1 条题解
-
0
[L] Deque(dp_l)题解
题意简述
太郎、次郎轮流从数列两端取数并得分,太郎想最大化 ,次郎想最小化。求最终 。
思路
状态
关键是把"两人得分差"作为唯一目标。设
$$f_{l,r} = \text{当前轮到某位玩家、面对区间 } a_l \dots a_r \text{ 时,该玩家最终能取得的(自己分} - \text{对手分)最大值}.$$由于两人目标对称(都最大化自己的差值),同一条递推对双方都成立——这正是"零和博弈"的转化。
转移
当前玩家要么取左端,要么取右端:
$$f_{l,r} = \max\big(a_l - f_{l+1,r},\; a_r - f_{l,r-1}\big),$$边界 。
为什么是减号?取走 后对手面对 ,他能取得的(对手分 − 自己分)是 ,所以自己的(自己分 − 对手分)是 。
答案:(此时轮到太郎)。
为什么不是
注意题面要的就是 本身,不是 。所以直接输出 。若要求 ,则 。
复杂度
时间 ,空间 ( B MB,AT 原题 1024 MB 无压力)。
参考代码
#include <cstdio> #include <algorithm> using namespace std; static long long f[3001][3001]; int main() { int n; scanf("%d", &n); static long long a[3001]; for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = 1; i <= n; i++) f[i][i] = a[i]; for (int len = 2; len <= n; len++) for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; f[l][r] = max(a[l] - f[l + 1][r], a[r] - f[l][r - 1]); } printf("%lld\n", f[1][n]); return 0; }易错点
- 输出的是 ,不要再除以 2(常见错误:算成先手得分)。
- 数组 72 MB,
static放在全局(BSS)里避免栈溢出。 - 区间长度从小到大枚举,保证 与 已算。
- 结果可能为负(样例 2 是 ),别用无符号类型。
数据说明
共 18 组:5 组官方样例(含 与 ); 边界;全相同、单调递增、单调递减; 随机; 的随机两组、递增、递减、 两值随机,覆盖最大值乘积。
- 1
信息
- ID
- 21
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者