257 字
1 分钟
CSES DP合集

O:Removal Game

思路#

我们令f(i,j)f(i,j)为在(i,j)(i,j)区间先手能取得的最大收益,我们显然根据可以从以(i+1,j)(i+1,j)和(i,j−1)(i,j-1)区间转移过来.也算是一个trick,如果从最后一局倒序看一场游戏,最后一把为最后一个人先手开始游戏,然后倒数第二把可以看作另一个人先手开一把游戏然后另一个人再进行最后一把 代码

#include <bits/stdc++.h>
#define N 1000005
#define pr pair<int,int>
#define ll long long
#define inf 100000000000
using namespace std;
ll n,m,ans;
const ll mod=1e9+7;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    vector<ll>s(n+5,0);
    vector<ll>pre(n+5,0);
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        pre[i]=pre[i-1]+s[i];
    }
    vector<vector<ll>>dp(n+5,vector<ll>(n+5,-1e16));
    for(int i=1;i<=n;i++) dp[i][i]=s[i];
    for(int i=n;i>=1;i--)
    {
        int len=i;
        for(int j=i;j<=n;j++)
        {
            if(i==j) continue;
            dp[i][j]=max({dp[i][j],pre[j]-pre[i-1]-dp[i+1][j],pre[j]-pre[i-1]-dp[i][j-1]});
        }
    }
    cout<<dp[1][n];
    return 0;
}
CSES DP合集
https://sanzenin.top/posts/obsidian/cses-dp合集/
作者
Sanzenin 凪
发布于
2026-01-25
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取

最后更新于 ,距今已过 295 天

部分内容可能已过时