题解：P13018 [GESP202506 七级] 调味平衡

考场上也不知道咋写出这种做法的，反正很玄学。

思路：

一开始看到就想到动规，但是就没想到怎么表示状态，但后来看到数据这么小，就想到了一种很笨的方法。就是使用

f[i][j][0]

表示当前决策到第

i

组调料，总酸度与总甜度的差值为

-j

时的总酸度与甜度之和最大值。

f[i][j][1]

表示当前决策到第

i

组调料，总酸度与总甜度的差值为

j

时的总酸度与甜度之和最大值。然后推了一会儿，不难发现，当

0 \le j \le a[i].cha

时，前一个转移的

j

值应该为

-(a[i].cha - j)

，同理，就可以推出当

j

在不同情况下的前一个转移项，注意不要把正负号弄错了。
于是转移方程就出来了，就是:

CPP

if(j <= a[i].cha) f[i][j][1] = max(f[i][j][1], f[i - 1][a[i].cha - j][0] + a[i].sum);
else f[i][j][1] = max(f[i][j][1], f[i - 1][j - a[i].cha][1] + a[i].sum); //正数情况 
			
if(-j <= a[i].cha) f[i][j][0] = max(f[i][j][0], f[i - 1][a[i].cha + j][0] + a[i].sum);
else f[i][j][0] = max(f[i][j][0], f[i - 1][-j - a[i].cha][1] + a[i].sum); //负数情况

注意：

1、就是这个差值调了好久，数组一定要开大点，不然会越界。
2、不要忘了不选的情况，就是：

CPP

f[i][j][1] = max(f[i][j][1], f[i - 1][j][1]);
f[i][j][0] = max(f[i][j][0], f[i - 1][j][0]);

这个要先写。

完整代码：

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e2 + 5, M = 1e5 + 5;

struct Node { int x, y, cha, sum; } a[N]; //cha 代表差值，sum 代表和 

int n;
int f[N][M * 2][2]; //注意要把数组开大，防止越界 

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y, a[i].cha = a[i].x - a[i].y, a[i].sum = a[i].x + a[i].y;
	memset(f, -0x3f, sizeof f); 
	for(int i = 1; i <= n; i++) { //初值 
		if(a[i].cha <= 0) f[i][-a[i].cha][0] = a[i].sum;
		else f[i][a[i].cha][1] = a[i].sum;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= M; j++) {
			f[i][j][1] = max(f[i][j][1], f[i - 1][j][1]);
			if(j <= a[i].cha) f[i][j][1] = max(f[i][j][1], f[i - 1][a[i].cha - j][0] + a[i].sum);
			else f[i][j][1] = max(f[i][j][1], f[i - 1][j - a[i].cha][1] + a[i].sum); //正数情况 
			
			f[i][j][0] = max(f[i][j][0], f[i - 1][j][0]);
			if(-j <= a[i].cha) f[i][j][0] = max(f[i][j][0], f[i - 1][a[i].cha + j][0] + a[i].sum);
			else f[i][j][0] = max(f[i][j][0], f[i - 1][-j - a[i].cha][1] + a[i].sum); //负数情况 
		}
	}
	cout << max(0LL, max(f[n][0][0], f[n][0][1])) << endl; //防止无解，要与 0 比 
	return 0;
}

题解：P13018 [GESP202506 七级] 调味平衡

文章操作

思路：

注意：

完整代码：

相关推荐

评论

题解：P13018 [GESP202506 七级] 调味平衡