luogu P1541 （dp）

传送门

题意：

有一条由(n)块瓷砖组成的路，每个瓷砖都有一个权值(a_i)。现在有个乌龟，有(m)张(4)种的卡片，分别是(1,2,3,4)。每张卡牌上的数字代表他能够向前走多少步。现在问题，这个乌龟用这(m)种卡片走到终点最多可以获取多少积分。

分析:

因为最终的结果跟每次选取卡牌的状态有关，故不妨设一个最暴力的(dp)式子：(dp[a][b][c][d][pos])代表现在有(a)张(1)卡牌，(b)张(2)卡牌，(c)张(3)卡牌，(d)张(4)卡牌，且当前的位置为(pos)。显然当前的位置可以从四个部分转移而来，因此有转移方程$$dp[a][b][c][d][pos]=max(dp[a-1][b][c][d][pos_1],dp[a][b-1][c][d][pos_2],dp[a][b][c-1][d][pos_3],dp[a][b][c][d-1][pos_4])+a[pos]$$。而显然当前的(pos)可以通过(a,b,c,d)计算得出，因此我们只需要开一个四维的状态记录即可。时间复杂度(mathcal{O}(n^4))

代码：

#include <bits/stdc++.h>
#define maxn 355
using namespace std;
int dp[50][50][50][50];
int a[maxn],mp[5];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    while(m--){
        int num;
        scanf("%d",&num);
        mp[num]++;
    }
    dp[0][0][0][0]=a[1];
    for(int i=0;i<=mp[1];i++){
        for(int j=0;j<=mp[2];j++){
            for(int k=0;k<=mp[3];k++){
                for(int kk=0;kk<=mp[4];kk++){
                    int cur=(i+j*2+k*3+kk*4+1);
                    if(i!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i-1][j][k][kk]+a[cur]);
                    if(j!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j-1][k][kk]+a[cur]);
                    if(k!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j][k-1][kk]+a[cur]);
                    if(kk!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j][k][kk-1]+a[cur]);
                }
            }
        }
    }
    printf("%d
",dp[mp[1]][mp[2]][mp[3]][mp[4]]);
    return 0;
}