題見洛谷
記憶化搜索
#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;int num[5],a0[400];int dp[40][40][40][40],ans=0;int n,m;int dfs(int x,int a,int b,int c,int d){ if(x==n){ return 0; } if(a) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a-1][b][c][d]?dp[a-1][b][c][d]+a0[x+1]:dfs(x+1,a-1,b,c,d)+a0[x+1]); if(b) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b-1][c][d]?dp[a][b-1][c][d]+a0[x+2]:dfs(x+2,a,b-1,c,d)+a0[x+2]); if(c) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c-1][d]?dp[a][b][c-1][d]+a0[x+3]:dfs(x+3,a,b,c-1,d)+a0[x+3]); if(d) dp[a][b][c][d]=max(dp[a][b][c][d],dp[a][b][c][d-1]?dp[a][b][c][d-1]+a0[x+4]:dfs(x+4,a,b,c,d-1)+a0[x+4]); return dp[a][b][c][d];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a0[i]); for(int i=1;i<=m;i++){ int x; scanf("%d",&x); num[x]++; } ans=dfs(1,num[1],num[2],num[3],num[4])+a0[1]; dp#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;int num[5],a0[400];int dp[40][40][40][40],ans=0;int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a0[i]); for(int i=1;i<=m;i++){ int x; scanf("%d",&x); num[x]++; } dp[0][0][0][0]=a0[1];//都用0張牌時，分數為a[1] int a=num[1],b=num[2],c=num[3],d=num[4]; for(int i1=0;i1<=a;i1++) for(int i2=0;i2<=b;i2++) for(int i3=0;i3<=c;i3++) for(int i4=0;i4<=d;i4++) { int x=0,step=i1+i2*2+i3*3+i4*4+1; if(i1) x=max(x,dp[i1-1][i2][i3][i4]); if(i2) x=max(x,dp[i1][i2-1][i3][i4]); if(i3) x=max(x,dp[i1][i2][i3-1][i4]); if(i4) x=max(x,dp[i1][i2][i3][i4-1]); dp[i1][i2][i3][i4]=x+a0[step];//+a0[step]移到max里面 不可以 會把dp[0][0][0][0]重新賦值為零 若要移，就需要將x賦值為a0[1]; } printf("%d",dp[a][b][c][d]); return 0; }新聞熱點
疑難解答
