DP为啥全WA了,大佬帮看看状态转移方程
查看原帖
DP为啥全WA了,大佬帮看看状态转移方程
468807
MagicDevil楼主2021/2/1 23:44
#include "bits/stdc++.h"
using namespace std;

int s[5],val[5][100];
int func(){
	int sum=0;
	for(int i=1;i<=4;i++){

		int dp[100][100],v=0;
		for(int j=1;j<=s[i];j++) v+=val[i][j];

		for(int x=1;x<=s[i];x++){
			for(int y=1;y<=v/2;y++){
                dp[x][y]=dp[x-1][y];
                if(y>=val[i][x])
                	dp[x][y]=max(dp[x-1][y], dp[x-1][y-val[i][x]]+val[i][x]);
			}
		}
        
		sum+=v-dp[s[i]][v/2];
	}
	return sum;
}

int main(){
	for(int i=1;i<=4;i++) scanf("%d",&s[i]);
	for(int i=1;i<=4;i++){
		for(int j=1;j<=s[i];j++) scanf("%d",&val[i][j]);
	}
	printf("%d",func());
	return 0;
}
2021/2/1 23:44
加载中...