[省选集训2022] 模拟赛6

A

题目描述

定义长度为 \(n\) 的好串 \(s\) 满足：

• \(|s_i-s_{i-1}|=1,i\in[2,n]\)
• \(s_i\geq\frac{s_{i+1}+s_{i-1}}{2},i\in[2,n-1]\)

给你长度为 \(n\) 的序列 \(a\) 和 \(v\)，分别表示原序列和价值序列。你每次可以选择一个原序列中的好串，将其删除之后剩下的串会前后拼接。设这次删除的长度是 \(l\)，那么会得分 \(v_l\)，问最大得分，不一定要把原序列删完。

\(n\leq 400,|v_i|\leq 10^5,a_i\leq10^9\)

解法

考虑求出 \(f[l][r]\) 表示把 \([l,r]\) 删完的最大得分，然后再用一维 \(dp\) 就可以拼出答案。

好串其实就是先以 \(1\) 的斜率上升、再以 \(1\) 的斜率下降的尖角形。发现还是不好做，我们可以考虑把它们拆成上升部分和下降部分，然后拼起来，拆分后的问题还是可以用 \(dp\) 解决。

具体来说我们设 \(up[l][r]\) 表示获取以 \(a_l\) 开头 \(a_r\) 结尾的上升段的最大价值，\(dn[l][r]\) 表示获取 \(a_l\) 开头 \(a_r\) 结尾的上升段的最大价值，那么转移枚举 \(i\) 使得 \(a_i+1=a_r/a_i-1=a_r\)：

\[up[l][r]\leftarrow up[l][i]+f[i+1][r-1] \]

\[dn[l][r]\leftarrow dn[l][i]+f[i+1][r-1] \]

那么如何把他们拼起来呢？我们枚举最高点 \(i\) 使得 \(a_i\geq a_l\and a_i\geq a_r\)，那么好串的长度一定是 \(2\cdot a_i-a_l-a_r\)，很容易写出转移：

\[f[l][r]\leftarrow up[l][i]+dn[i][r]+v[2\cdot a_i-a_l-a_r+1] \]

但是 \(a_l,a_r\) 也可以不在一个好串中，这时候我们需要枚举分界点将他们分开：

\[f[l][r]\leftarrow f[l][i]+f[i+1][r] \]

此外只有上升段和下降段需要单独讨论一下，时间复杂度 \(O(n^3)\)

总结

设计多个 \(dp\) 状态，互相转移的方法是很值得思考的。其实我感觉它的原理还是__分步思想__，把一个较为复杂的问题拆分成若干个部分解决，这些部分中可能又蕴含子问题。

#include 
#include 
using namespace std;
const int M = 405;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[M],v[M],dp[M],f[M][M],up[M][M],dn[M][M];
void upd(int &x,int y) {x=max(x,y);}
signed main()
{
	freopen("good.in","r",stdin);
	freopen("good.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) v[i]=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int l=n;l>=1;l--)
	for(int r=l;r<=n;r++)
	{
		f[l][r]=up[l][r]=dn[l][r]=-inf;
		up[l][l]=dn[l][l]=0;
		for(int i=l;i=a[l] && a[i]>=a[r]) upd(f[l][r],
				up[l][i]+dn[i][r]+v[2*a[i]-a[l]-a[r]+1]);
		}
		if(a[l]>=a[r])
			upd(f[l][r],dn[l][r]+v[a[l]-a[r]+1]);
		if(a[l]<=a[r])
			upd(f[l][r],up[l][r]+v[a[r]-a[l]+1]);
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];
		for(int j=1;j<=n;j++)
			upd(dp[i],dp[j-1]+f[j][i]);
	}
	printf("%lld\n",dp[n]);
}