非01背包做法,31分
查看原帖
非01背包做法,31分
742157
ZYK_luogu楼主2023/8/10 10:52

这个题我想的是求最大子序列和,个人感觉没错,但是只有36分。

dp[i][1] : 从 1 - n 中奶牛智商的最大和
dp[i][2] : 从 1 - n 中奶牛情商的最大和
dp[i][3] : 从 1 - n 中奶牛智商情商总和的最大值
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 405;
int n, s[N], f[N], dp[N][4], res = -1e9;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d%d", &s[i], &f[i]);
	for (int i = 1; i <= n; i ++) {
		dp[i][1] = s[i], dp[i][2] = f[i], dp[i][3] = s[i] + f[i];
		for (int j = 1; j < i; j ++) 
			if(dp[j][1] + s[i] >= 0 && dp[j][2] + f[i] >= 0 && dp[j][3] + s[i] + f[i] > dp[i][3]) {
				dp[i][1] += dp[j][1] + s[i];
				dp[i][2] += dp[j][2] + f[i];
				dp[i][3] = max(dp[i][3], dp[j][3] + s[i] + f[i]);
			}
		if (dp[i][1] >= 0 && dp[i][2] >= 0)
			res = max(res, dp[i][3]);
	}
	printf("%d", max(res, 0));
	return 0;
}
2023/8/10 10:52
加载中...