算法:区间 DP
时间复杂度:$O(n^2)$
定义状态 $1$
$f[i][j]$ 表示先手面临区间 $[i, j]$ 时的最大得分。
当取 $w[i]$ 时,则 $f[i][j] = w[i] + {\textstyle \sum_{k = i + 1}^{j}}w[k] - f[i + 1][j]$。
当取 $w[j]$ 时,则 $f[i][j] = w[j] + {\textstyle \sum_{k = i}^{j - 1}}w[k] - f[i][j - 1]$。
二者取其 $max$ 即可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], s[N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
s[i] = s[i - 1] + w[i];
}
for (int len = 1; len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
f[i][j] = max(w[i] + s[j] - s[i] - f[i + 1][j], w[j] + s[j - 1] - s[i - 1] - f[i][j - 1]);
}
}
cout << f[1][n] << ' ' << s[n] - f[1][n] << endl;
return 0;
}
定义状态 $2$
$f[i][j]$ 表示在区间 $[i, j]$ 时,先手和后手的最大差值得分。
当取 $w[i]$ 时,$f[i][j] = w[i] - f[i + 1][j]$。
当取 $w[j]$ 时,$f[i][j] = w[j] - f[i][j - 1]$。
两者取其 $max$ 即可。
解释:以第一种情况为例,f[i][j] 表示在区间 [i, j] 时 A - B 的最大值,当选了w[i]时,而f[i + 1][j] 表示在区间 [i + 1, j] 时 B - A 的最大值,这时取一下相反数即可得到 A - B 的最大值
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], f[N][N];
int main()
{
cin >> n;
int sum = 0;
for (int i = 0; i < n; ++i) cin >> w[i], sum += w[i];
for (int len = 1; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
f[i][j] = max(w[i] - f[i + 1][j], w[j] - f[i][j - 1]);
}
}
cout << (sum + f[0][n - 1]) / 2 << ' ' << (sum - f[0][n - 1]) / 2 << endl;
return 0;
}
orz
为什么不是7 + 9 + 5 - 4 - 2 - 2呢,然后一边是21,一边是8,根本理解不了啊,这是什么意思啊?
两个玩家都是最优策略,不存在一方每次拿最大的,另一方每次拿最小的,而且应该每个玩家都有上帝视角。
样例:4,7,2,9,5,2
玩家1:想要拿7和9,第一轮就不能拿4,于是拿2
4,7,2,9,5
玩家2:拿4,拿5结果差不多,都会让下一轮玩家1拿到7,或者9,(7-4)<(9-5)这边拿4
7,2,9,5
玩家1:这时候肯定拿7
2,9,5
玩家2:还是一样不管拿2,5都会让9被玩家1拿走,所有拿5,尽可能保证自己更大。
2,9
然后玩家1拿2-7-9
玩家2拿4-5-2这样子
哦,对哦,是这样的,这个部分我懂了,谢谢啦!
啊?