描述
题解
Petra 和 Jan 轮流取糖果,每个糖果有 x 和
首先我们按照 Petra 的贪心策略进行排序,然后分析可以发现(假定先手是 Jan ), Jan 的操作无非两种,一种是拿 Petra 下次要取的糖果,另一种就是拿别的,简单的说就是抢与不抢的问题,而前 i 个糖果,
这里并没有结束,因为我们还要保证
另外,如果先手是 Petra ,自然是没有争议,毕竟是贪心嘛,所以直接从序列第二个开始考虑即可,默认第一个被 Petra 贪心取走了。
很巧妙的贪心与动归的结合问题,刘汝佳老师好像说这个题可以完全贪心搞,有些懵,不是特别了解怎么搞……当然,上述题解的代码并没有体现出来多少贪心部分,可能这个题思路上是贪心和动归的结合,但是解法上可以只用贪心或者只用动归就能解决。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_LEN_NAME = 11;
const int MAXN = 1010;
struct Node
{
int x, y;
bool operator < (const Node &rhs) const
{
if (x != rhs.x)
{
return x > rhs.x;
}
return y < rhs.y;
}
} arr[MAXN];
int n;
int dp[MAXN][MAXN >> 1];
int cost[MAXN][MAXN >> 1];
char name[MAX_LEN_NAME];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%s", &n, name);
int sum = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &arr[i].x, &arr[i].y);
sum += arr[i].x;
}
sort(arr + 1, arr + 1 + n);
memset(dp, 0, sizeof(dp));
memset(cost, 0, sizeof(cost));
int cur = 0;
int i = name[0] == 'P' ? 2 : 1;
for (; i <= n; ++i)
{
++cur;
int t = (cur + 1) >> 1;
for (int j = 1; j <= t; ++j)
{
int &ans = dp[i][j] = dp[i - 1][j];
cost[i][j] = cost[i - 1][j];
if (j == 1 || dp[i - 1][j - 1])
{
int tmp = dp[i - 1][j - 1] + arr[i].y;
if (tmp > ans)
{
ans = tmp;
cost[i][j] = cost[i - 1][j - 1] + arr[i].x;
}
else if (tmp == ans)
{
cost[i][j] = min(cost[i][j], cost[i - 1][j - 1] + arr[i].x);
}
}
}
}
printf("%d %d\n", sum - cost[n][(cur + 1) >> 1], dp[n][(cur + 1) >> 1]);
}
return 0;
}