题解：P1389 一个关于序列的游戏

区间 dp 好题，思路容易考虑不周或假掉。

首先看到这个数据范围，一眼区间 dp，然后考虑如何做。

我们观察一下这个符合要求的区间的限制，一个是

|a_i-a_{i+1}|\leq 1

这个很好处理，但是下一个条件转化成式子就是

a_{i+1} \geq \frac{1}{2} (a_{i}+a_{i+2})

，这是啥意思？

我们一眼发现这个东西得是一个凸的东西，一直单增或单减显然合法，然后考虑发现单峰也是合法的！

我们可以考虑证明：

若存在单峰，则

a_{i+2}=a_{i+1}+1=a_i+2

，然后将这个式子带入条件:

a_i+1=a_{i+1}=\frac{1}{2}(a_i+a_i+2)=a_i+1

则可以证明是正确的，而单谷却不行，读者可以自行证明。

那找到了这个性质之后就可以 dp 了。

设

f_{i,j}

表示将

[i,j]

这一段全部删光的最大分数。

设

g_{i,j}

表示将

[i,j]

这一段删成单调递增，且保留 $i$ 和 $j$ 位置的最大分数。

设

h_{i,j}

表示将

[i,j]

这一段删成单调递减且保留 $i$ 和 $j$ 位置的最大分数。

考虑如何转移，对于

g

，显然有：

g_{i,j}=g_{i,k}+f_{k+1,j-1}

类似地，对于

h

，有：

g_{i,j}=g_{i,k}+f_{k+1,j-1}

那这个时候可能会有人有疑问了，假如说我删去

[i,j]

中间的一段

[l,r]

，满足

i<l\leq r<j

，那这样岂不是转移不到？

答案是可以转移到的，我们考虑每一次进行转移都会留下来右端点

j

，然后在下一次转移的时候当我的

k

为现在的

j

的时候我又会删掉一些新的，和我直接删掉一部分是等价的。

而我们对于

f

的转移，则有两种。

$i$ 和 $j$ 不同时被消掉，即 $f_{i,j}=f_{i,k}+f_{k+1,j}$
先删掉一部分，最后将 $l$ 和 $r$ 同时删掉，即 $f_{i,j}=g_{i,k}+h_{k,j}+v_{a_k\times 2-a_i-a_j+1}$ ，这其中加的东西是因为是单峰的，将中间的减去两边的相加 $+1$ 即可算出长度。

最后统计答案，简单 dp 计算即可。

#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=155;
int _=1,n,ans=0,v[N],a[N],dp[N],f[N][N],g[N][N],h[N][N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("good.in","r",stdin);
	freopen("good.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) v[i]=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		memset(g,-0x3f,sizeof(g));memset(h,-0x3f,sizeof(h));
		memset(f,-0x3f,sizeof(f));
		for(int i=1;i<=n;i++) g[i][i]=h[i][i]=f[i][i-1]=0,f[i][i]=v[1];
		for(int len=2;len<=n;len++){
			for(int i=1;i+len-1<=n;i++){
				int j=i+len-1;
				for(int k=i;k<j;k++){
					if(a[k]+1==a[j]) g[i][j]=max(g[i][j],g[i][k]+f[k+1][j-1]);
					if(a[k]-1==a[j]) h[i][j]=max(h[i][j],h[i][k]+f[k+1][j-1]);
					f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
				}for(int k=i;k<=j;k++){
					int t=a[k]+a[k]-a[i]-a[j]+1;
					if(t<0||t>n) continue;
					f[i][j]=max(f[i][j],g[i][k]+h[k][j]+v[a[k]+a[k]-a[i]-a[j]+1]);
				}
			}
		}for(int i=1;i<=n;i++){
			dp[i]=dp[i-1];
			for(int j=0;j<i;j++) dp[i]=max(dp[i],dp[j]+f[j+1][i]);
			ans=max(ans,dp[i]);
		}printf("%lld\n",ans);
	}return 0;
}

题解：P1389 一个关于序列的游戏

文章操作

相关推荐

评论

题解：P1389 一个关于序列的游戏