动规背包 50pts 求调
查看原帖
动规背包 50pts 求调
818180
wjzj楼主2023/8/27 22:59
#include<iostream>
#include<algorithm>
using namespace std;
int a[21],i,j,k,s[5],t;
int dp[21][1201];
int main(){
for(i=1;i<=4;i++) scanf("%d",&s[i]);
for(i=1;i<=4;i++){
	int sum=0;
	for(j=1;j<=s[i];j++){
		scanf("%d",&a[j]);
		sum+=a[j];
	}
	for(j=1;j<=s[i];j++){
		for(k=1;k<=sum/2;k++){
			if(k<a[j]) dp[j][k]=dp[j-1][k];
			else dp[j][k]=max(dp[j-1][k],dp[j][k-a[j]]+a[j]);
		}
	}
	t+=sum-dp[s[i]][sum/2];	
}
printf("%d",t);
return 0;
}
2023/8/27 22:59
加载中...