1 条题解

  • 0
    @ 2026-11-12 21:57:40

    [L] Deque(dp_l)题解

    题意简述

    太郎、次郎轮流从数列两端取数并得分,太郎想最大化 X−YX - Y,次郎想最小化。求最终 X−YX - Y。

    思路

    状态

    关键是把"两人得分差"作为唯一目标。设

    $$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),$$

    边界 fl,l=alf_{l,l} = a_l。

    为什么是减号?取走 ala_l 后对手面对 [l+1,r][l+1, r],他能取得的(对手分 − 自己分)是 fl+1,rf_{l+1,r},所以自己的(自己分 − 对手分)是 al−fl+1,ra_l - f_{l+1,r}。

    答案:f1,Nf_{1,N}(此时轮到太郎)。

    为什么不是 (S+f)/2(S + f)/2

    注意题面要的就是 X−YX - Y 本身,不是 XX。所以直接输出 f1,Nf_{1,N}。若要求 XX,则 X=(S+f1,N)/2X = (S + f_{1,N})/2。

    复杂度

    时间 O(N2)≤9×106O(N^2) \le 9\times10^6,空间 O(N2)O(N^2)(30002×83000^2 \times 8 B =72= 72 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;
    }
    

    易错点

    1. 输出的是 X−YX-Y,不要再除以 2(常见错误:算成先手得分)。
    2. 数组 72 MB,static 放在全局(BSS)里避免栈溢出。
    3. 区间长度从小到大枚举,保证 fl+1,rf_{l+1,r} 与 fl,r−1f_{l,r-1} 已算。
    4. 结果可能为负(样例 2 是 −80-80),别用无符号类型。

    数据说明

    共 18 组:5 组官方样例(含 −80-80 与 49999999954999999995);N=1/2/3N=1/2/3 边界;全相同、单调递增、单调递减;N=10/100/500N=10/100/500 随机;N=3000N=3000 的随机两组、递增、递减、{1,109}\{1,10^9\} 两值随机,覆盖最大值乘积。

    • 1

    信息

    ID
    21
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者