P1541 [NOIP 2010 提高组] 乌龟棋

Koei · 2025-10-03 17:23:59 · 个人记录

状态：dp_{a,b,c,d}

状态表示为当使用a张走1步，b张2步，c张3步，d张4步的最大得分

对于这个状态的转移方程为：

而sum=1+a+b\times 2+c\times 3+d\times 4为什么要+1呢？

因为初始点为1而 a+b\times 2+c\times 3+d\times 4 计算出的是往后移动的距离，所以还要 +1

而且初始点为1所以初始化为 dp_{0,0,0,0}=e_1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,m;
int e[maxn],g[5];
int dp[41][41][41][41];
int main(){
    cin>>n>>m;
    for(int i(1);i<=n;i++){
        cin>>e[i];
    }
    for(int i(1);i<=m;i++){
        int x;
        cin>>x;
        g[x]++;
    }
    dp[0][0][0][0]=e[1];
    for(int a(0);a<=g[1];a++){
        for(int b(0);b<=g[2];b++){
            for(int c(0);c<=g[3];c++){
                for(int d(0);d<=g[4];d++){
                    int sum(1+a+b*2+c*3+d*4);
                    if(a!=0){
                        dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]+e[sum]);
                    }
                    if(b!=0){
                        dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]+e[sum]);
                    }
                    if(c!=0){
                        dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]+e[sum]);
                    }
                    if(d!=0){
                        dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]+e[sum]);
                    }
                }
            }
        }
    }
    cout<<dp[g[1]][g[2]][g[3]][g[4]]<<'\n';
    return 0;
}