吃菜

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Cai
{
    // 味道、价格、对第二个人的价值
    int w, c, val;
};
bool cmp(Cai &a, Cai &b)
{
    if (a.c != b.c)
        return a.c > b.c;
    return a.w > b.w;
}
int n;
Cai a[5005];
// f[i][j]：前 i 道菜，后手吃了 j 道的最大价值
int f[5005][2505];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].w >> a[i].c;
        a[i].val = a[i].w - a[i].c;
    }
    sort(a + 1, a + n + 1, cmp);
    memset(f, 0xc0, sizeof(f)); //-INF/2
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= i / 2; j++) // 最多吃一半
        {
            // 第 i 道菜给先手吃
            f[i][j] = f[i - 1][j];
            // 第 i 道菜自己吃
            if (j > 0 && i >= j * 2 && f[i - 1][j - 1] != -1) // 能吃的上第i道菜
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i].val);
            // cout << i << " " << j << " " << f[i][j] << endl;
        }
    }
    cout << f[n][n / 2] << endl;
    return 0;
}