专栏文章

P11642 题解

AAC_notonlyAC
P11642题解参与者 1已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqd5tl4
此快照首次捕获于
2025/12/04 02:51
3 个月前
此快照最后确认于
2025/12/04 02:51
3 个月前
查看原文
萌新第一次写题解，不明之处见谅

【MX-J10】梦熊 J 组 · 猕猴桃赛 &「TAOI」Round 3（同步赛）T2 （P11642） 题解

考虑dpdp。
首先先设置状态 fif_i ,表示到第 ii 位的最大和，可这样并不好列出状态转移方程，因为题目中要求修改的区域为连续的子段，这样很有可能修改多个连续的子段，这不是我们能接受的。
因此我们需要再添一维，即 fi,jf_{i,j}。
而这么大的空间肯定不行，所以第二维只能是 0/1 ，或其他小数字，类似于结构体。
因为每到新的一位，只有可能有三种状态：要么未使用过区间变，要么正在使用区间变，要么已使用过区间变。于是我们可以设 fi,0f_{i,0} 的状态为到第 ii 位，且已使用过区间变的最大和，fi,1f_{i,1} 的状态为到第 ii 位，且正在使用区间变的最大和，fi,2f_{i,2} 的状态为到第 ii 位，且未使用过区间变的最大和。
fi,0f_{i,0} 只能由 fi−1,0f_{i-1,0} 或 fi−1,1f_{i-1,1} 转移来（要么维持以前的已使用过区间变的状态，要么由以前的正在使用区间变的状态转移来）
fi,1f_{i,1} 只能由 fi−1,1f_{i-1,1} 或 fi−1,2f_{i-1,2} 转移来（要么维持以前的正在使用区间变的状态，要么由以前的未使用过区间变的状态转移来）
fi,2f_{i,2} 只能由 fi−1,2f_{i-1,2} 转移来（这个就不用多说了吧）
其实 fi,2f_{i,2} 本质上是前缀和。
这样的话，状态转移方程就很好写了：
fi,0=max⁡(fi−1,0,fi−1,1)+aif_{i,0}=\max(f_{i-1,0},f_{i-1,1})+a_i
fi,1=max⁡(fi−1,1,fi−1,2)+xf_{i,1}=\max(f_{i-1,1},f_{i-1,2})+x
fi,2=fi−1,2+aif_{i,2}=f_{i-1,2}+a_i
最终将 fn,0,fn,1,fn,2f_{n,0},f_{n,1},f_{n,2} 取个最大值就行了。不难。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,a[100005],sum[100005],f[100005][3],maxn;
int main()
{
	cin>>n>>x;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(ll i=1;i<=n;i++)
	{
		f[i][2]=f[i-1][2]+a[i];
		f[i][1]=max(f[i-1][1],f[i-1][2])+x;
		f[i][0]=max(f[i-1][0],f[i-1][1])+a[i];
	}
	cout<<max(max(f[n][0],f[n][1]),f[n][2]);
}

评论

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

正在加载评论...