【DP】乌龟棋

「爱情、让人受尽委屈。」 2024-03-24 10:23 35阅读 0赞

这状态设计的真的牛逼

本来想了个暴力DP，前i个数选了j个卡片，选的是第k个卡片，然后搞个状压记录选了哪几种卡片，因为卡片一共就4种

但是它说的不能选是指同一种是可以重复选的

所以肯定不能这么搞

但是我觉得我的思路还是可以的，**就是看到小数据应该想到暴力或状压**

正解应该是

状态设计：

设dp\[i\]\[j\]\[k\]\[z\]为所有第1/2/3/4种卡片选了i/j/k/z个的最大收益

然后阶段其实就是选一片片的卡片，因此可以考虑枚举这次选的是哪张卡片

然后要计算贡献，贡献取决于你跳到哪个点了

这个是可以算出来的，就是a\[i+2\*j+3\*k+4\*k\]

然后算一算贡献就好了捏

[312. 乌龟棋 - AcWing题库][312. _ - AcWing]

![fe6a790e888b485cb2bcd1caf3cdc4cd.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=352;
    const int mxe=1e6+10;
    int n,m,x;
    int a[mxn],mp[mxn];
    int dp[2][44][44][44];
    void solve(){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<m;i++){
            cin>>x;
            mp[x]++;
        }
        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 z=0;z<=mp[4];z++){
                        int t=a[i+2*j+3*k+4*z];
                        dp[i&1][j][k][z]=max(dp[i&1][j][k][z],t);
                        if(i>=1) dp[i&1][j][k][z]=max(dp[i&1][j][k][z],dp[(i-1)&1][j][k][z]+t);
                        if(j>=1) dp[i&1][j][k][z]=max(dp[i&1][j][k][z],dp[i&1][j-1][k][z]+t);
                        if(k>=1) dp[i&1][j][k][z]=max(dp[i&1][j][k][z],dp[i&1][j][k-1][z]+t);
                        if(z>=1) dp[i&1][j][k][z]=max(dp[i&1][j][k][z],dp[i&1][j][k][z-1]+t);
                    }
                }
            }
        }
        cout<<dp[mp[1]&1][mp[2]][mp[3]][mp[4]]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[312. _ - AcWing]: https://www.acwing.com/problem/content/description/314/
[fe6a790e888b485cb2bcd1caf3cdc4cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f70de83e9fdc48c0bcd9408aa73c52b7.png