ib
1
说实话，当时我做这道题的时候内心是激动\(≧▽≦)/和崩溃%>_<%的，其间我一些SB做法就不提了（一直是在局部最优徘徊→ →），后来在CA神和肖大爷的帮助下，从一维数组改成一个四位数组进行dp，然后就过了。。。就过了。。。#include<iostream>#include<cstdio>using namespace std;int ff(int a,int b,int c,int d){return max(max(a,b),max(c,d));}int a[400],b[4],ans[41][41][41][41];//a数组存储每个格子的价值，b[i]表示能走i步的卡片数量多少，ans的四维分别表示四种卡片的使用，ans[m][n][k][l]用来存储用m张1，n张2，k张3和l张4所获得的最大价值。main(){int n,m,x;cin>>n>>m;for (int i=1;i<=n;i++) cin>>a[i];for (int i=1;i<=m;i++){cin>>x;b[x]++;}ans[0][0][0][0]=a[1];//初始为起点价值for (int i=0;i<=b[1];i++)for (int j=0;j<=b[2];j++)for (int k=0;k<=b[3];k++)for (int l=0;l<=b[4];l++){int x1=0,x2=0,x3=0,x4=0;int value=a[i+j*2+k*3+l*4+1];if (i>=1) x1=ans[i-1][j][k][l]+value;if (j>=1) x2=ans[i][j-1][k][l]+value;if (k>=1) x3=ans[i][j][k-1][l]+value;if (l>=1) x4=ans[i][j][k][l-1]+value;ans[i][j][k][l]+=ff(x1,x2,x3,x4);}cout<<ans[b[1]][b[2]][b[3]][b[4]];}总结一下做法就是一个个去试，但不同于深搜（dfs），时间复杂度大大减小，但四重循环还是谨慎使用的好，毕竟这个题目每种不大于40；最多40^4=2560000，，爆不了的
版权声明：本文为博主原创文章，未经博主允许不得转载。
往往教导我们大家要好好学习天天向上，要永不言弃坚持到底百折不挠宁死不屈，
