题意:给你一个一维棋盘,棋盘上有对应的分数,然后给你若干张牌,每张牌的数字代表它可以使小乌龟移动的距离(1,2,3,4)给定的牌必须全部消耗完且最后一定可以到达终点,询问可以获得的最大的分数?
分析:首先这个题很容易陷入对棋盘进行DP的错误思路,其实这里的思路是开4维DP,
DP【i】【j】【k】【m】:在消耗(1,2,3,4)牌的数目分别是(i,j,k,m)的情况下
我们获得的最大的分数,显然答案就是DP【cnt[1]】【cnt[2]】【cnt[3]】【cnt[4]】
那么状态如何更新呢?
发现:我们消耗的牌的数目决定了我们当前在哪一格
t = i*1+j*2+k*3+m*4+1 就是我们当前所处的位置
当前状态最后一个不同的递推点在于选择权值多大的牌来使用,例如
if(i) DP【i】【j】【k】【m】= max(DP[i][j][k][m],DP[i-1][j][k][m]+w[t]);
....同理可得出替其他的
注意还需要初始化一下我们的DP【0】【0】【0】【0】 = w【1】;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n,m;
ll w[N];
ll cnt[10];
ll f[45][45][45][45];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i];while(m--){int a;cin>>a;cnt[a]++;}f[0][0][0][0] = w[1];for(ll a=0;a<=cnt[1];a++)for(ll b=0;b<=cnt[2];b++)for(ll c=0;c<=cnt[3];c++)for(ll d=0;d<=cnt[4];d++){ll t=a*1+b*2+c*3+d*4+1;ll &tem = f[a][b][c][d];if(a)tem = max(tem,f[a-1][b][c][d]+w[t]);if(b)tem = max(tem,f[a][b-1][c][d]+w[t]);if(c)tem = max(tem,f[a][b][c-1][d]+w[t]);if(d)tem = max(tem,f[a][b][c][d-1]+w[t]);}cout<<f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];}
还是欠缺知识,慢慢积累吧,成功在于不懈的积累,学到这里发现,信息学和数学很大的不一样的地方在于,它很难有统一的现成模式(通法)直接套用,它需要见大量的习题来积累经验,这需要非常大的抵抗这种困难的毅力。