1 条题解

  • 0
    @ 2025-5-11 15:51:21
    #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;
    }
    
    • 1

    信息

    ID
    1706
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    8
    已通过
    4
    上传者