E. Vasya and Binary String

分析：

　　对于长度为x的一段序列，我们可以dp出消除的过程的最优方案，背包即可。

　　然后区间dp，可以先合并完所有的点，即没相同的一段区间合并为一个点。设f[i][j][k]表示消完区间[i,j]和这段区间后面k个元素最大值，其中k个元素的颜色与点j的颜色相同。

　　转移：可以首先将j和后面k个元素消除，然后消除[i,j-1]。也可以枚举一个和j颜色相同的点m，然后分别先消除[m+1,r-1]，剩下的区间就和后面k个连在一起了，再求出这段区间的答案。

　　复杂度$O(n^4)$，但是跑不满，再记忆化一下，31ms。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int n, cnt;

LL a[N], f[N], g[N][N][N];

char s[N];

struct Node { int size, col; } b[N];

void init() {

    for (int i = ; i <= n; ++i)

        for (int j = i; j <= n; ++j) f[j] = max(f[j], f[j - i] + a[i]);

    int now = ;

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

        if (s[i] == s[i - ]) now ++;

        else cnt ++, b[cnt].size = now, b[cnt].col = s[i - ] - '', now = ;

    }

    ++cnt; b[cnt].size = now, b[cnt].col = s[n] - '';

}

LL DP(int l,int r,int k) {

    if (l == r) return f[b[l].size + k];

    if (~g[l][r][k]) return g[l][r][k];

    LL res = DP(l, r - , ) + f[b[r].size + k];

    for (int i = l; i < r - ; ++i)

        if (b[i].col == b[r].col) res = max(res, DP(i + , r - , ) + DP(l, i, b[r].size + k));

    return g[l][r][k] = res;

}

int main() {

    n = read();

    scanf("%s", s + );

    for (int i = ; i <= n; ++i) a[i] = read();

    init();

    memset(g, -, sizeof(g));

    cout << DP(, cnt, );

    return ;

}

巴特西

CF 1107 E. Vasya and Binary String

E. Vasya and Binary String

最新文章

热门文章