P1541 [NOIP 2010 提高组] 乌龟棋

状态：

dp_{a,b,c,d}

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

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

dp_{a,b,c,d}=max(dp_{a,b,c,d},dp_{a-1,b,c,d}+\text{当前点的分数$e_{sum}$})\\ dp_{a,b,c,d}=max(dp_{a,b,c,d},dp_{a,b,-1c,d}+\text{当前点的分数$e_{sum}$})\\ dp_{a,b,c,d}=max(dp_{a,b,c,d},dp_{a,b,c-1,d}+\text{当前点的分数$e_{sum}$})\\ dp_{a,b,c,d}=max(dp_{a,b,c,d},dp_{a,b,c,d-1}+\text{当前点的分数$e_{sum}$})

而

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

CPP

#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;
}

P1541 [NOIP 2010 提高组] 乌龟棋

文章操作

相关推荐

评论

P1541 [NOIP 2010 提高组] 乌龟棋