背包。
将物品按照petra的贪心思想排序
假设Jan先手，对于第i (1~n)个物品，他的背包大小为（i+1）/2，因为对于前i个物品，Jan最多拿走（i+1) /2个。
那么petra的值就是Jan拿剩下的。
代码：
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define lson o<<1 #define rson o<<1|1 #define CLR(A, X) memset(A, X, sizeof(A)) using namespace std; typedef long long LL; typedef pair<int, int> PII; const double eps = 1e-10; int dcmp(int x){if(fabs(x)<eps) return 0; return x<0?-1:1;} const int N = 1e3+5; const LL MOD = 1e9+7; int dp[N], cost[N]; PII a[N]; bool cmp(PII a, PII b) { return a.fi>b.fi || (a.fi==b.fi&&a.se<b.se); } int main() { int T; cin >> T; while(T--) { int n, sum = 0; char s[10]; scanf("%d", &n); scanf("%s", s); for(int i = 1; i <= n; i++) { scanf("%d%d", &a[i].fi, &a[i].se); sum += a[i].fi; } sort(a+1, a+n+1, cmp); if(s[0] == 'P') { for(int i = 1; i < n; i++) a[i] = a[i+1]; n--; } CLR(dp, -1); CLR(cost, -1); dp[0] = cost[0] = 0; for(int i = 1; i <= n; i++) { for(int j = (i+1)/2; j >= 1; j--) if(~dp[j-1]) { if(dp[j-1]+a[i].se > dp[j]) { dp[j] = dp[j-1]+a[i].se; cost[j] = cost[j-1]+a[i].fi; } else if(dp[j-1]+a[i].se == dp[j]) { cost[j] = min(cost[j-1]+a[i].fi, cost[j]); } } } printf("%d %d\n", sum-cost[(n+1)/2], dp[(n+1)/2]); } return 0; }