求助:dp
查看原帖
求助:dp
253936
simonG楼主2022/4/7 22:21
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXM=40,MAXN=400;
int f[MAXM+2][MAXM+2][MAXM+2][MAXM+2];
int n,m,v[MAXN+5],p[MAXM+5],cnt[5];
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++)
		scanf("%d",&v[i]);
	for(int i=1; i<=m; i++) {
		scanf("%d",&p[i]);
		cnt[p[i]]++;
	}
	f[0][0][0][0]=v[1];
	for(int i=0; i<=cnt[1]; i++)
		for(int j=0; j<=cnt[2]; j++)
			for(int k=0; k<=cnt[3]; k++)
				for(int l=0; l<=cnt[4]; l++) {
					int t=i+2*j+3*k+4*l+1;
					if(i) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+v[t]);
					if(j) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+v[t]);
					if(k) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+v[t]);
					if(l) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+v[t]);
				}
	printf("%d\n",f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
	return 0;
}

40分,求调,其他WA

2022/4/7 22:21
加载中...