题解：P1541 [NOIP2010 提高组] 乌龟棋

· · 题解

基础动态规划。

这道题的题目条件显然满足阶段性和无后效性，那么有一个直观的思路就是把当前所处格子和四种卡片的使用次数作为状态。

但是如果按照上面的想法，数组空间是无法开下的，所以我们稍微变一下思路，把四种卡片的使用数量作为状态，对于当前所处格子的话可以直接计算出来，这样数组空间是 40^4\approx 2e6 的，可以满足。

那么思路就明确了，我们设 dp_{i,j,k,c} 表示四种卡片分别使用 i,j,k,c 张时所能获得的最大分数，然后用四重循环分别枚举四种卡片的使用数量，计算当前到达的位置 x，那么有转移方程：

dp_{i,j,k,c}=\max(dp_{i-1,j,k,c},dp_{i,j-1,k,c},dp_{i,j,k-1,c}，dp_{i,j,k,c-1})+a_x

转移的时候判断一下数组下标是否越界即可。

因为题目保证刚好用光所有卡片，那么如果设 f_i 表示数字为 i 的卡片的数量，答案显然为 dp_{f_1,f_2,f_3,f_4}。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
    return w*s;
}
const int mod=998244353;
const int maxn=400;
const int inf=2e9+10;
const double eps=1e-10;
int n,m,a[maxn],b[5];
int dp[42][42][42][42];
signed main(){
#ifdef Lydic
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)b[read()]++;
    dp[0][0][0][0]=a[1];
    for(int i=0;i<=b[1];i++){
        for(int j=0;j<=b[2];j++){
            for(int k=0;k<=b[3];k++){
                for(int c=0;c<=b[4];c++){
                    int x=1+i+j*2+k*3+c*4;
                    if(i)dp[i][j][k][c]=max(dp[i][j][k][c],dp[i-1][j][k][c]+a[x]);
                    if(j)dp[i][j][k][c]=max(dp[i][j][k][c],dp[i][j-1][k][c]+a[x]);
                    if(k)dp[i][j][k][c]=max(dp[i][j][k][c],dp[i][j][k-1][c]+a[x]);
                    if(c)dp[i][j][k][c]=max(dp[i][j][k][c],dp[i][j][k][c-1]+a[x]);
                }
            }
        }
    }
    cout<<dp[b[1]][b[2]][b[3]][b[4]];
    return 0;
}