bzoj3255 一个关于序列的游戏-白红宇

bzoj3255 一个关于序列的游戏

阅读量：5157 次

发布时间：2019-06-13

本文共 2649 字，大约阅读时间需要 8 分钟。

题意是啥

给你一个数列，可以任意删去一段，记其长度为$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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          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 
          
            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;}