1 条题解
-
0
#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
- 上传者