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

Retoayd · 2025-07-01 23:17:11 · 题解

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

思路：

一开始看到就想到动规，但是就没想到怎么表示状态，但后来看到数据这么小，就想到了一种很笨的方法。就是使用 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 在不同情况下的前一个转移项，注意不要把正负号弄错了。
于是转移方程就出来了，就是:

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、不要忘了不选的情况，就是：

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]);

这个要先写。

完整代码：

#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;
}