CodeVS/1068

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
乌龟棋	★★☆☆☆	答案正确	100	2014/11/04 20:37:43	数组不够大（60）

题意

在1~N格子中，要从第一个格子走到第N个，每走到一个格子可以获得格子不同的价值。有至多四种前进步数（四种乌龟卡），每种步数只能使用固定次数，求到终点能获得的最大价值总和。

题解

嗯。四重for的DP，转移方程是:

    f(每种卡片分别用了i,j,k,l张)=
        当前所在格子的价值
        +
        max{
            f(每种卡片分别用了i-1,j,k,l张),
            f(每种卡片分别用了i,j-1,k,l张),
            f(每种卡片分别用了i,j,k-1,l张),
            f(每种卡片分别用了i,j,k,l-1张)
        };

DP方程蛮好理解的，但是太久没做真的不好想。

代码

1068.cpp代码已折叠 展开折叠内容

#include<map> #include<cstdio> #include<iterator> #include<algorithm> std::map<int,int> cardM; int n,m,f[50][50][50][50]={},score[500]={},cardN[4]={},cardP[4]={}; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&score[i]); for(int i=1,pace;i<=m;++i) { scanf("%d",&pace); cardM[pace]++; } int p=0; for(std::map<int,int>::iterator i=cardM.begin();i!=cardM.end();++i,++p) { cardP[p]=i->first; cardN[p]=i->second; } for(int i=0;i<=cardN[0];++i) for(int j=0;j<=cardN[1];++j) for(int k=0;k<=cardN[2];++k) for(int l=0;l<=cardN[3];++l) { int s=i*cardP[0]+j*cardP[1]+k*cardP[2]+l*cardP[3]+1; if(i)f[i][j][k][l]=std::max(f[i][j][k][l],f[i-1][j][k][l]+score[s]); if(j)f[i][j][k][l]=std::max(f[i][j][k][l],f[i][j-1][k][l]+score[s]); if(k)f[i][j][k][l]=std::max(f[i][j][k][l],f[i][j][k-1][l]+score[s]); if(l)f[i][j][k][l]=std::max(f[i][j][k][l],f[i][j][k][l-1]+score[s]); } printf("%d",f[cardN[0]][cardN[1]][cardN[2]][cardN[3]]+score[1]); return 0; }