题目:P1541 乌龟棋
感谢大神的题解(他的写的特别好)
写一下我对他的代码的理解吧(哎,蒟蒻就这能这样...)
代码:
#include<bits/stdc++.h> #define ll long long using namespace std; ll num[350+100]; ll p[5]; ll f[41][41][41][41]; int main() {ios::sync_with_stdio(false);ll n,m;//n格子数,m牌数cin>>n>>m;for(ll i=1;i<=n;i++)cin>>num[i];ll x;for(ll i=1;i<=m;i++)cin>>x,p[x]++;//偷懒用逗号隔开 f[0][0][0][0]=num[1];for(ll a=0;a<=p[1];a++)for(ll b=0;b<=p[2];b++)for(ll c=0;c<=p[3];c++)for(ll d=0;d<=p[4];d++){ll r=1+1*a+2*b+3*c+4*d;if(a>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+num[r]);//如果有牌出if(b>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+num[r]);if(c>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+num[r]);if(d>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+num[r]);}cout<<f[p[1]][p[2]][p[3]][p[4]]<<endl; }
思路:
每个牌有四种,建立一个四维数组f[a][b][c][d]表示当现在使用了a张走一位牌,b...,c...,d张走四位牌后能获得的最大数字
然后输入数据的时候准备一个数组p[5],把a,b,c,d牌数量分别放入1,2,3,4位
然后
for(a=0~p[1])for(b=0~p[2])for(b=0~p[3])for(b=0~p[4])//表示遍历a,b,c,d全部情况,我们要的是答案f[p[1]][p[2]][p[3]][p[4]]
所以要想办法递推到f[p[1]][p[2]][p[3]][p[4]]
用4个max,计算每一次的最大f[a][b][c][d],
那个递推式中:
ll r=1+1*a+2*b+3*c+4*d;//r表示当前的位置,+1是,比如说a=b=c=d=0,但是他是在第一位,所以初始位是1 if(a>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+num[r]);//如果有牌出 if(b>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+num[r]); if(c>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+num[r]); if(d>=1) f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+num[r]);
中,a>=1是判断是否可以出牌
对于f[a-1][b][c][d]+num[r]的意思就是如果更新出了a牌之后的的数字总数,f[a][b][c][d]就是不出牌的数字总数,其实就是不变
