【1】做题心得 - 2025 NOIP #64 - T1【动态规划】【区间 DP】

· · 题解

h1w 我赛时为什么为什么没做出来怎么会是呢。考虑直接 dp。设 f_{0/1,i,j} 为区间 i,j 顺序 / 逆序能获得的最大收益，简单做。g_{i,j} 为前 i 个有 j 次修改的情况。计算是简单的。

反思：赛事没有往区分方向这方面想，一直在思考正确策略。然后 dp 状态也设计过，问题是状态设计太过复杂，甚至空间爆炸了没绷住。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=616;
int n,k;
ll p[N],f[2][N][N],g[N][N];
int main(){
    freopen("box.in","r",stdin);
    freopen("box.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    memset(g,-0x3f,sizeof(g));
    ll ans=g[0][0];
    g[0][0]=0;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            ll su=0;
            for(int i=r;i>=l;i--) su+=p[i], f[0][l][r]+=su,su=max(su,0ll);
            su=0;
            for(int i=l;i<=r;i++) su+=p[i], f[1][l][r]+=su,su=max(su,0ll);
        }
        g[l][0]=f[0][1][l];
    }
    for(int r=1;r<=n;r++)for(int l=0;l<r;l++)
        for(int i=1;i<=k;i++)
            g[r][i]=max(g[r][i],max(g[l][i]+f[0][l+1][r],g[l][i-1]+f[1][l+1][r]));
    for(int i=0;i<=k;i++)
        ans=max(ans,g[n][i]);
    cout<<ans;
    return 0;
}