专栏文章

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

EExFish
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5rjfz
此快照首次捕获于
2025/12/01 21:01
3 个月前
此快照最后确认于
2025/12/01 21:01
3 个月前
查看原文
h1w 我赛时为什么为什么没做出来怎么会是呢。考虑直接 dp。设 f0/1,i,jf_{0/1,i,j} 为区间 i,ji,j 顺序 / 逆序能获得的最大收益，简单做。gi,jg_{i,j} 为前 ii 个有 jj 次修改的情况。计算是简单的。
反思：赛事没有往区分方向这方面想，一直在思考正确策略。然后 dp 状态也设计过，问题是状态设计太过复杂，甚至空间爆炸了没绷住。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...