题意

给定一个长度为n的序列，你可以进行若干次操作：

选择一个区间，删掉，并获得Val[Len]的得分，Len为这个区间的长度：

其中这个区间满足：

1.相邻两个数差的绝对值为1

2.每个数都大于相邻两个数的平均数

问最大得分。

解法

一眼过去，得到一个可能是O(n^4)的做法。

设f[i][j]表示删除掉[i,j]这个区间的最大得分。

然后发现只有这个转移不了，然后又多设了一个g[i][j][0/1]，表示以a[i]开头的，以a[j]结尾的上升或下降的最大得分。

然后发现这个好像要多存一个个数，然后很倦生，然后就弃疗了。

赛后发现，其实标算跟我的做法差不多，多存一维个数可以用上升序列的性质直接算。

然后打着打着又发现了一个问题。

f[i][j]<-g[i][k]+g[k][j]的合并有点奇怪。

然后水过了之后再看标，恍然大悟。

靠这样转移就可以把两个g拼接起来了。

Code

#include<bits/stdc++.h>

#define ll long long

#define fo(i,x,y) for(int i=x;i<=y;i++)

#define fd(i,x,y) for(int i=x;i>=y;i--)

using namespace std;

const int maxn=407,Inf=0x7fffffff;

int n,Val[maxn],a[maxn];

int Up[maxn][maxn],Dn[maxn][maxn];

void getUpDn(){

	fo(i,1,n){

		Up[i][i]=0;

		fo(j,i+1,n){

			if (Up[i][j-1]) Up[i][j]=Up[i][j-1];

			else if (a[j]==a[j-1]+1) Up[i][j]=0;

			else Up[i][j]=j;

		}

	}

	fo(i,1,n){

		Dn[i][i]=0;

		fo(j,i+1,n){

			if (Dn[i][j-1]) Dn[i][j]=Dn[i][j-1];

			else if (a[j]==a[j-1]-1) Dn[i][j]=0;

			else Dn[i][j]=j;

		}

	}

}

void Init(){

	scanf("%d",&n);

	fo(i,1,n) scanf("%d",&Val[i]);

	fo(i,1,n) scanf("%d",&a[i]);

	getUpDn();

}

int Check(int l,int r,int L=0,int R=0){

	if (L){

		if (r-l+1==0) return Check(L,R);

		else if (R-L+1==0)  return Check(l,r);

		else{

			int x=Up[l][r];

			if (x==0){

				if (a[r]+1==a[L]) return Check(L,R);

				else if (a[r]-1==a[L]) return (Dn[L][R]==0)*2;

				else return 0;

			}else{

				if (Dn[x-1][r]==0 && a[r]-1==a[L]) return (Dn[L][R]==0)*2;

				else return 0;

			}

		}

	}else{

		if (l==r) return 1;

		else{

			int x=Up[l][r];

			if (x==0) return 1;

			else return (Dn[x-1][r]==0)*2;

		}

	}

}

int f[maxn][maxn],g[maxn],h[maxn][maxn][2],Ans=0;

void getF(){

	fo(Len,2,n)

		fo(i,1,n){

			int j=i+Len-1;

			if (j>n) break;

			fo(k,i,j-1){

				if (a[k]+1==a[j]) h[i][j][0]=max(h[i][j][0],h[i][k][0]+f[k+1][j-1]);

				if (a[k]-1==a[j]) h[i][j][1]=max(h[i][j][1],h[i][k][1]+f[k+1][j-1]);

			}

			fo(k,i,j-1){

				f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);

			}

			fo(k,i,j-1)

				if (h[i][k][0]>-1e8 && h[k][j][1]>-1e8)

							f[i][j]=max(f[i][j],h[i][k][0]+h[k][j][1]+Val[a[k]-a[i]+a[k]-a[j]+1]);

			if (h[i][j][0]>-1e8) f[i][j]=max(f[i][j],h[i][j][0]+Val[a[j]-a[i]+1]);

			if (h[i][j][1]>-1e8) f[i][j]=max(f[i][j],h[i][j][1]+Val[a[i]-a[j]+1]);

		}

}

void getG(){

	g[0]=0;

	fo(i,1,n){

		g[i]=g[i-1];

		fo(j,0,i-1){

			g[i]=max(g[i],g[j]+f[j+1][i]);

		}

	}

}

void Solve(){

	fo(i,1,n) fo(j,1,n) f[i][j]=h[i][j][0]=h[i][j][1]=-1e9;

	fo(i,1,n){

		f[i][i-1]=0;

		fo(j,i,n){

			if (Check(i,j)) f[i][j]=Val[j-i+1];

			else f[i][j]=-1e9;

			if (j>i) h[i][j][0]=h[i][j][1]=-1e9;

			else h[i][j][0]=h[i][j][1]=0;

		}

	}

	getF();

	getG();

	Ans=g[n];

}

void Print(){

	printf("%d\n",Ans);

}

int main(){

	freopen("1.in","r",stdin);

	freopen("1.out","w",stdout);

	Init();

	Solve();

	Print();

	return 0;

}

巴特西

【JZOJ5179】【NOI2017模拟6.29】哈哈

题意

解法

Code

最新文章

热门文章