Problem
Source: BSOJ 1744
Description
wind 发明了一个好玩的游戏,叫小杉一起玩。但小杉玩了十几盘,总是输,他想知道是不是从一开始他就注定要输。
这个游戏是这样的,wind 先写下一排数。既然是一排,当然有首尾咯。wind 和小杉每次只能从这排数的头或尾取一个数。最后谁取的数的和多,谁就赢了。
假如你是小杉,请算出你最多能取到的和。wind 的智商是很高的(怪不得小杉一直输),你必须知道他总是做出最优决策。
Input
多组输入数据。
每组测试数据的第一行仅有一个数 $n (n \leq 2000)$
第二行也仅有一个数,0 表示 wind 先取数,1 表示小杉先取数
第三行有 $n$ 个数,是 wind 给出的一排数,这 $n$ 个数均不超过 $1e6$
Output
对每组测试数据输出一行,仅有一个整数 $s$,表示小杉最多能取到多少数
Sample Input
1
1
1
Sample Output
1
Solution
$f(i,j)$:先取数的人在第 $i$ 个数到第 $j$ 个数之间能取到的最大和
$s(i,j)$:第 $i$ 个数到第 $j$ 个数的部份和
状态转移方程:
\[f(i,j)= \max \Big \{ a(i)+s(i+1,j)-f(i+1,j),a(j)+s(i,j-1)-f(i,j-1) \Big \}\]解释:先取的人从 $i$ 到 $j$ 取得最大和的情况,要么是该人先取 $i$,加上 $i+1$ 到 $j$ 的总和,再减去对方先取时从 $i+1$ 到 $j$ 取得的最大和;或是该人先取 $j$,加上 $i$ 到 $j-1$ 的总和,再减去对方先取时从 $i$ 到 $j-1$ 取得的最大和(因为两人都按同一策略取)。
Code
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[2005], s[2005], f[2005][2005];
int n, t;
void Dp() {
for(int l = 2; l <= n; l++)
for(int i = 1; i <= n - l + 1; i++) {
int j = i + l - 1;
f[i][j] = max(a[i] + s[j] - s[i] - f[i+1][j], a[j] + s[j-1] - s[i-1] - f[i][j-1]);
}
if(t == 0) printf("%d\n",s[n] - f[1][n]);
else printf("%d\n", f[1][n]);
}
int main() {
while(scanf("%d%d", &n, &t) != EOF) {
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i-1] + a[i];
f[i][i] = a[i];
}
Dp();
}
return 0;
}
NEXTNosknah 的宝藏