UVa 12260 Free Goodies

题目描述

Petra\texttt{Petra}Petra和Jan\texttt{Jan}Jan收到nnn个礼物，每个礼物对Petra\texttt{Petra}Petra的价值为pip_ipi​，对Jan\texttt{Jan}Jan的价值为jij_iji​。两人轮流挑选礼物，通过抛硬币决定谁先开始。Petra\texttt{Petra}Petra采用贪心策略：每次选择对自己价值pip_ipi​最高的礼物，如果有多个礼物pip_ipi​相同，则选择对Jan\texttt{Jan}Jan价值jij_iji​最低的礼物。Jan\texttt{Jan}Jan的策略则是最优化自己的总价值，并且在多个选择获得相同价值时，让Petra\texttt{Petra}Petra的总价值尽可能大。

给定初始的抛硬币结果（谁先手）以及每个礼物对两人的价值，求最终两人各自获得的总价值（按各自的评估标准）。

输入格式

• 第一行：测试用例数量TTT（最多100100100个）。
• 每个测试用例：
  • 一行：整数nnn（1≤n≤10001 \le n \le 10001≤n≤1000），礼物数量。
  • 一行：字符串，Petra\texttt{Petra}Petra或Jan\texttt{Jan}Jan，表示先手的人。
  • nnn行：每行两个整数pip_ipi​和jij_iji​（0≤pi,ji≤10000 \le p_i, j_i \le 10000≤pi​,ji​≤1000），分别表示Petra\texttt{Petra}Petra和Jan\texttt{Jan}Jan对第iii个礼物的评估价值。

输出格式

每个测试用例输出一行，包含两个整数：Petra\texttt{Petra}Petra获得的总价值和Jan\texttt{Jan}Jan获得的总价值。

题目分析

本题的关键在于理解两人的策略差异并设计合适的状态转移方程。

1. 策略分析

• Petra\texttt{Petra}Petra的贪心策略：她的选择顺序是固定的，总是选择当前剩余礼物中对自己价值最高（ppp最大）的礼物，ppp相同时选对Jan\texttt{Jan}Jan价值最低（jjj最小）的礼物。因此，我们可以将所有礼物按照Petra\texttt{Petra}Petra的优先级排序：ppp降序，ppp相同时jjj升序。排序后，Petra\texttt{Petra}Petra总是从前往后依次选取礼物。
• Jan\texttt{Jan}Jan的最优策略：Jan\texttt{Jan}Jan知道Petra\texttt{Petra}Petra的选取顺序，他可以在自己的回合中选择任意一个礼物，目标是在游戏结束时最大化自己的总价值，并且在多个最优方案中选择让Petra\texttt{Petra}Petra总价值最大的那个。

2. 问题转化

由于Petra\texttt{Petra}Petra的选取顺序固定，问题可以转化为：在排序后的礼物列表中，Jan\texttt{Jan}Jan可以选择“抢占”某些Petra\texttt{Petra}Petra将要拿的礼物。具体来说，每个礼物有两个状态：被Jan\texttt{Jan}Jan拿走或被Petra\texttt{Petra}Petra拿走。

Jan\texttt{Jan}Jan的决策可以看作：对于排序后的第iii个礼物，Jan\texttt{Jan}Jan可以选择是否抢占它。如果抢占，Jan\texttt{Jan}Jan获得jij_iji​价值，Petra\texttt{Petra}Petra失去pip_ipi​价值（因为她拿不到这个礼物了）；如果不抢占，Petra\texttt{Petra}Petra正常拿走该礼物，获得pip_ipi​价值。

3. 动态规划设计

定义状态：

• dp[i][k]dp[i][k]dp[i][k]：考虑前iii个礼物，Jan\texttt{Jan}Jan抢占了kkk个时，Jan\texttt{Jan}Jan能获得的最大总价值。
• val[i][k]val[i][k]val[i][k]：在上述情况下，Jan\texttt{Jan}Jan抢占的礼物的Petra\texttt{Petra}Petra价值之和（即Petra\texttt{Petra}Petra因此损失的价值）。

状态转移：
对于第iii个礼物（排序后）：

1. Jan\texttt{Jan}Jan不抢占：Petra\texttt{Petra}Petra拿走该礼物。此时Jan\texttt{Jan}Jan的价值不变，Petra\texttt{Petra}Petra的损失不变。
   • dp[i][k]=dp[i−1][k]dp[i][k] = dp[i-1][k]dp[i][k]=dp[i−1][k]
   • val[i][k]=val[i−1][k]val[i][k] = val[i-1][k]val[i][k]=val[i−1][k]
2. Jan\texttt{Jan}Jan抢占：Jan\texttt{Jan}Jan拿走该礼物。此时Jan\texttt{Jan}Jan的价值增加jij_iji​，Petra\texttt{Petra}Petra的损失增加pip_ipi​。
   • dp[i][k]=dp[i−1][k−1]+jidp[i][k] = dp[i-1][k-1] + j_idp[i][k]=dp[i−1][k−1]+ji​
   • val[i][k]=val[i−1][k−1]+pival[i][k] = val[i-1][k-1] + p_ival[i][k]=val[i−1][k−1]+pi​

决策时优先最大化dp[i][k]dp[i][k]dp[i][k]（Jan\texttt{Jan}Jan的价值），如果dp[i][k]dp[i][k]dp[i][k]相同，则选择val[i][k]val[i][k]val[i][k]较小的方案（让Petra\texttt{Petra}Petra损失更小，即Petra\texttt{Petra}Petra最终价值更大）。

4. 先手影响

Jan\texttt{Jan}Jan最多能抢占的礼物数量取决于谁先手：

• Petra\texttt{Petra}Petra先手：两人轮流，Jan\texttt{Jan}Jan最多能抢占⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋个礼物。
• Jan\texttt{Jan}Jan先手：Jan\texttt{Jan}Jan可能多抢一个，最多能抢占⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉个礼物。

在动态规划过程中，对于前iii个礼物，Jan\texttt{Jan}Jan最多能抢占的数量numnumnum为：

• Petra\texttt{Petra}Petra先手：num=i/2num = i/2num=i/2
• Jan\texttt{Jan}Jan先手：num=(i+1)/2num = (i+1)/2num=(i+1)/2

5. 结果计算

设所有礼物的Petra\texttt{Petra}Petra价值总和为totalPtotalPtotalP。在动态规划结束后，我们遍历所有可能的kkk（Jan\texttt{Jan}Jan抢占的数量），找到dp[n][k]dp[n][k]dp[n][k]最大的方案，如果多个方案dp[n][k]dp[n][k]dp[n][k]相同，选择val[n][k]val[n][k]val[n][k]最小的。

最终：

• Jan\texttt{Jan}Jan的总价值 =dp[n][k]dp[n][k]dp[n][k]
• Petra\texttt{Petra}Petra的总价值 =totalP−val[n][k]totalP - val[n][k]totalP−val[n][k]

时间复杂度

排序复杂度O(nlog⁡n)O(n \log n)O(nlogn)，动态规划状态数O(n2)O(n^2)O(n2)，总时间复杂度O(n2)O(n^2)O(n2)，在n≤1000n \le 1000n≤1000时可行。

代码实现

// Free Goodies// UVa ID: 12260// Verdict: Accepted// Submission Date: 2025-12-10// UVa Run Time: 0.120s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structCandy{intp,j;};boolcmp(constCandy&a,constCandy&b){if(a.p!=b.p)returna.p>b.p;returna.j<b.j;}intmain(){intt;cin>>t;while(t--){intn;cin>>n;string first;cin>>first;vector<Candy>candies(n);inttotalP=0;for(inti=0;i<n;i++){cin>>candies[i].p>>candies[i].j;totalP+=candies[i].p;}sort(candies.begin(),candies.end(),cmp);vector<vector<int>>dp(n+1,vector<int>(n+1,0));vector<vector<int>>val(n+1,vector<int>(n+1,0));for(inti=1;i<=n;i++){intnum;if(first=="Petra"){num=i/2;}else{num=(i+1)/2;}for(intj=1;j<=num;j++){dp[i][j]=dp[i-1][j];val[i][j]=val[i-1][j];intcandJan=dp[i-1][j-1]+candies[i-1].j;intcandVal=val[i-1][j-1]+candies[i-1].p;if(candJan>dp[i][j]){dp[i][j]=candJan;val[i][j]=candVal;}elseif(candJan==dp[i][j]&&candVal<val[i][j]){val[i][j]=candVal;}}}intmaxJan=0,minVal=0;intmaxTake;if(first=="Petra"){maxTake=n/2;}else{maxTake=(n+1)/2;}for(intj=1;j<=maxTake;j++){if(dp[n][j]>maxJan){maxJan=dp[n][j];minVal=val[n][j];}}intpetraVal=totalP-minVal;cout<<petraVal<<" "<<maxJan<<endl;}return0;}