区间dp模板

该死的csdn登陆不上去了，为了防止区间dp模板丢失，在这里再存一份

然后是左右取数字的问题，我记得20年的时候我应该看过这题，是有一个数列，前后取若干个数字，问先手能取最大值

那个时候没怎么看懂这个，今天做完题突然理解了，返回去看那个题

首先每次可以固定左右必选，那么左边必选的最大收益是当前的值 + 左边[l + 1,r]的最大值

那么右边同理，因为双方play optimally，所以我们不能光记录先手的最大值，还需要记录后手的最大值

如果先手play optimally，那么后手的最大值就是区间总价值 - 先手左/右最大值

然后我们在选的时候也要把这个考虑进去，因为和max是反复切换的，所以我们先手后手可以易手，如果先手取a[l]没有比后手取a[l]更优，那么此时易手，对右边同理

就有dp方程

dpl[l][r] = max(dp[l + 1][r] + a[l] , min[l + 1][r] + a[l])
dpr[l][r] = max(dpr[l][r - 1] + a[r], minn[l][r - 1] + a[r])

然后对于minn，我们可以用区间和 - 最大先手收益，就能获得后手收益

int tot = sum[r] - sum[l - 1];
minn[l][r] = min(tot - dpl[l][r], tot - dpr[l][r]);

合并

//区间dp
    rep(i, 1, n){
        rep(l, 1, n - i){
            int r = l + i;
            ll tot = sum[r] - sum[l - 1];
            dpl[l][r] = max(dpl[l + 1][r] + a[l], minn[l + 1][r] + a[l]);
            dpr[l][r] = max(dpr[l][r - 1] + a[r], minn[l][r - 1] + a[r]);
            minn[l][r] = min(tot - dpl[l][r], tot - dpr[l][r]);
        }
    }
    ll ans = max(dpl[1][n], dpr[1][n]);

总之如果找博弈类问题答案，输出赢还是输，那么不要陷入细枝末节的博弈中去，考虑怎么转移到必胜态，

对于找数值问题，我们可以先手后手同时计算维护，先手对自身和后手最大化，然后后手对先手留下的结果最小化，minmax交题