bzoj3255 一个关于序列的游戏

题意是啥

给你一个数列，可以任意删去一段，记其长度为$s$，得到$val_s$的价值，问你最大价值和为多少..

其中这一段数要满足成一个上凸且相邻数差为$1$

显然，删掉一段数后剩下的左右会相邻..

%%%

伏地膜一发liaoliao.. 虽然他的代码被我拍出错了

记$f_{i,j}$为$[i,j]$这一段全部选的最优价值

$g_{i,j,k}$为$[i,j]$这一段存在一个长度为$k$的符合要求的子序列的最优价值

那么我们的任务就是把$f$和$g$交替维护

对于一个区间$[x,y]$

我们找到比$a_x$大$1$的那些数所在的位置，记为$p$

对于$x\leq p\leq y$

$g_{x,y,k}=f_{x+1,p-1}+g_{p,y,k-1}$

同样找到比$a_y$大$1$的那些数所在的位置，记为$p$

对于$x\leq p\leq y$

$g_{x,y,k}=f_{p+1,y-1}+g_{x,p,k-1}$

那么解决$f$的维护就是易如反(huan)掌了

$$f_{x,y}=max(max(g_{x,y,k}),max(f_{x,i}+f_{i+1,y})),\ k\in [1,y-x+1],\ i\in [x,y)$$

然后的话就是维护可以不选的情况了..

相信很简单..

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

using namespace std;

const int Maxn = 160;

const int inf = 0x7fffffff;

int f[Maxn][Maxn][2], g[Maxn][Maxn][Maxn];

int val[Maxn], a[Maxn];

int b[Maxn], bl, ab[Maxn];

int n;

vector <int> vec[Maxn];

int _max(int x, int y) { return x > y ? x : y; }

int main() {

	int i, j, k;

	scanf("%d", &n);

	for(i = 1; i <= n; i++) scanf("%d", &val[i]);

	for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];

	sort(b+1, b+n+1);

	bl = unique(b+1, b+n+1) - (b+1);

	for(i = 1; i <= n; i++){

		ab[i] = lower_bound(b+1, b+bl+1, a[i]) - b;

		vec[ab[i]].push_back(i);

	}

	for(i = 0; i <= n+1; i++) for(j = 0; j <= n+1; j++){

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

		for(k = 0; k <= n; k++) g[i][j][k] = -inf;

	}

	f[1][0][0] = f[1][0][1] = 0;

	for(i = 1; i <= n; i++){

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

		f[i][i][1] = val[1];

		f[i][i][0] = _max(0, val[1]);

		g[i][i][1] = 0;

	}

	for(k = 2; k <= n; k++){

		for(int x = 1; x <= n-k+1; x++){

			int y = x+k-1;

			for(int kk = 2; kk <= k; kk++){

				int sz;

				if(b[ab[x]]+1 == b[ab[x]+1]){

					sz = vec[ab[x]+1].size();

					for(i = 0; i < sz; i++){

						int p = vec[ab[x]+1][i];

						if(p < x || p > y) continue;

						if(g[p][y][kk-1] == -inf) continue;

						g[x][y][kk] = _max(g[x][y][kk], f[x+1][p-1][1]+g[p][y][kk-1]);

					}

				}

				if(b[ab[y]]+1 == b[ab[y]+1]){

					sz = vec[ab[y]+1].size();

					for(i = 0; i < sz; i++){

						int p = vec[ab[y]+1][i];

						if(p < x || p > y) continue;

						if(g[x][p][kk-1] == -inf) continue;

						g[x][y][kk] = _max(g[x][y][kk], f[p+1][y-1][1]+g[x][p][kk-1]);

					}

				}

				if(g[x][y][kk] != -inf) f[x][y][1] = _max(f[x][y][1], g[x][y][kk]+val[kk]);

			}

			for(i = x; i < y; i++){

				f[x][y][1] = _max(f[x][y][1], f[x][i][1]+f[i+1][y][1]);

				f[x][y][0] = _max(f[x][y][0], f[x][i][0]+f[i+1][y][0]);

			}

			f[x][y][0] = _max(f[x][y][0], f[x][y][1]);

		}

	}

	printf("%d\n", f[1][n][0]);

	return 0;

}

Tips

非常好人的贴出了liaoliao ac代码的wa数据

input:

11

-14 -53 68 43 0 0 0 0 0 0 0

3 5 6 8 7 7 4 0 6 1 5

output:

80

Review

感觉这样的题也是第一次见..

挺不错的一道题.. 这种处理方式也值得我去好好品味..

巴特西

bzoj3255 一个关于序列的游戏

题意是啥

%%%

Code

Tips

Review

最新文章

热门文章