题解【Codeforces859C】Pie Rules

一道需要一定思考的 \(\text{DP}\) 。

设 \(dp_i\) 表示第 \(i\) 步走的人能得到的最大分数， \(sum_i\) 表示 \(\sum_{j=i}^n a_j\) ，即 \(sum_i\) 为序列 \(\{a_i\}\) 的后缀和。

状态转移方程： \(dp_i=\max\{dp_{i+1}, sum_{i+1}-dp_{i+1}+a_i\}\) 。

解释一下：

\(dp_{i+1}\) 的意思是第 \(i+1\) 个决策的人将 \(a_{i+1}\) 给了对方，自己还是第 \(i\) 个决策的人；
\(sum_{i+1}-dp_{i+1}+a_i\) 的意思是第 \(i+1\) 个决策的人不是第 \(i\) 个决策的人，第 \(i+1\) 个决策的人得到了 \(dp_{i+1}\) 的分数，则第 \(i+1\) 轮后第 \(i\) 个决策的人得到了 \(sum_{i+1} - dp_{i+1}\) 的分数，第 \(i\) 个决策的人在第 \(i\) 轮还得到了 \(a_i\) 的分数。

可能比较难理解…

代码写起来也很简单：

#include <bits/stdc++.h>

#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

int n, m, a[55], sum[55], dp[55];

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi();

	for (int i = 1; i <= n; i+=1) a[i] = gi();

	for (int i = n; i >= 1; i-=1) sum[i] = sum[i + 1] + a[i];

	for (int i = n; i >= 1; i-=1) dp[i] = max(dp[i + 1], sum[i + 1] - dp[i + 1] + a[i]);

	printf("%d %d\n", sum[1] - dp[1], dp[1]);

	return 0;

}

巴特西

题解【Codeforces859C】Pie Rules

最新文章

热门文章