蓝桥杯刷题-乌龟棋

312. 乌龟棋 - AcWing题库

/*  
    状态表示：f[b1,b2,b3,b4]表示所有第 i种卡片使用了 bi张的走法的最大分值。
    状态计算：将 f[b1,b2,b3,b4]表示的所有走法按最后一步选择哪张卡片分成四类：
    第 i类为最后一步选择第 i种卡片。比如 i=2，
    则这一类的最大分值是 f[b1,b2−1,b3,b4]+score[b1+2b2+3b3+4b4]
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 360, M = 41;

int n, m;
int score[N];
int f[M][M][M][M];

int main()
{
    int b[5] = {0};
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &score[i]);

    for (int i = 0; i < m; i ++ )
    {
        int t;
        scanf("%d", &t);
        b[t] ++ ;
    }

    for (int A = 0; A <= b[1]; A ++ )
        for (int B = 0; B <= b[2]; B ++ )
            for (int C = 0; C <= b[3]; C ++ )
                for (int D = 0; D <= b[4]; D ++ )
                {
                    int t = score[A + B * 2 + C * 3 + D * 4];
                    int &v = f[A][B][C][D];
                    v = t;
                    if (A) v = max(v, f[A - 1][B][C][D] + t);
                    if (B) v = max(v, f[A][B - 1][C][D] + t);
                    if (C) v = max(v, f[A][B][C - 1][D] + t);
                    if (D) v = max(v, f[A][B][C][D - 1] + t);
                }

    printf("%d\n", f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
}

原文地址：https://blog.csdn.net/2301_79973431/article/details/137837136

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！