Codeforces1107E. Vasya and Binary String

题目链接

本题也是区间dp，但是需要保存的信息很多，是1还是0，有多少个连续的，那我们可以预处理，将所有的连续缩合成1个字符，那么字符串就变成了一个01交替的串，我们任意的消除1个部分，一定能引起连锁反应，像消消乐

我们设dp_i,j,k为区间[i,j]，j后面有k个与j相同的元素，若j与前面的i-j-1一起消，状态转移为：dp_i,j,k=dp_i,m,k+siz[j]+dp_m+1,j-1,0，(m与j的字符相同)意思是合并i到m,m+1到j-1合并后，将i到m与j再合并,如果j单独消，dp_i,j,k=dp_i,j-1,0+f[siz[j]+k]

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

typedef pair<int,int> pii;

const int maxn = 105;

char s[maxn];

LL dp[maxn][maxn][maxn], f[maxn], cost[maxn];

int n, siz[maxn], bit[maxn], cnt;

void prework() {

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

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

            f[j] = max(f[j], f[j-i] + cost[i]);

    cnt = 0;

    int now = 0;

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

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

        else {

            siz[++cnt] = now;

            bit[cnt] = s[i-1] - '0';

            now = 1;

        }

    }

    siz[++cnt] = now, bit[cnt] = s[n] - '0';

}

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

    if(l == r) return dp[l][r][k] = f[siz[r]+k];

    if(dp[l][r][k] != -1) return dp[l][r][k];

    LL t = DP(l, r-1, 0) + f[siz[r] + k];

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

        if(bit[i] == bit[r])

            t = max(t, DP(l, i, k+siz[r])+DP(i+1, r-1, 0));

    return dp[l][r][k] = t;

}

void run_case() {

    cin >> n;

    cin >> (s+1);

    for(int i = 1; i <= n; ++i) cin >> cost[i];

    prework();

    memset(dp, -1, sizeof(dp));

    cout << DP(1, n, 0);

}

int main() {

    ios::sync_with_stdio(false), cin.tie(0);

    cout.flags(ios::fixed);cout.precision(10);

    //int t; cin >> t;

    run_case();

    cout.flush();

    return 0;

}

转自

https://blog.csdn.net/litble/article/details/87290658

巴特西

Codeforces1107E. Vasya and Binary String

最新文章

热门文章