[NOIP2010 提高组] 乌龟棋

题目大意

有四种卡片,它们分别可以让你前进1格,2格,3格和4格.在前进的道路上到达每个格子都会得到对应的积分.现在分别给出四种卡片的数量,求用完所有卡片能获得的最大积分和

思路

由于卡片只有4种,且每种的数量不超过20张,所以想到开四维dp,用dp[i][j][k][z]来表示用掉i张卡片4,j张卡片3,k张卡片2,z张卡片1时能获得的最大积分和.状态转移方程为:

dp[i][j][k][z] = max(dp[i][j][k][z],dp[i - 1][j][k][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j-1][k][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k-1][z]+a[t]);
dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k][z - 1] + a[t]);

代码如下:

#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define N 356
int dp[41][41][41][41];
int a[N],b[5];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m,x; cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= m; i++) {
        cin >> x;
        //分别统计四种卡片的数目
        b[x]++;
    }
    int t;
    //在第一格的分数
    dp[0][0][0][0]=a[1];
    for (int i = 0; i <= b[4]; i++) {
        for (int j = 0; j <= b[3]; j++) {
            for (int k = 0; k <= b[2]; k++) {
                for (int z = 0; z <= b[1]; z++) {
                    //用t来表示到达第几格
                    t = 1+i*4 + j*3 + k*2 + z;
                    if (i)dp[i][j][k][z] = max(dp[i][j][k][z],dp[i - 1][j][k][z]+a[t]);
                    if(j)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j-1][k][z]+a[t]);
                    if (k)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k-1][z]+a[t]);
                    if(z)dp[i][j][k][z] = max(dp[i][j][k][z], dp[i][j][k][z - 1] + a[t]);
                }
            }
        }
    }
    cout << dp[b[4]][b[3]][b[2]][b[1]];
    return 0;
}