CF1107E Vasya and Binary String解题报告

解题报告

CF1107E Vasya and Binary String解题报告：

更好的阅读体验

前言

有两道比较相似的题目，可以先做完：CF1132F Clear the String与SP6340 ZUMA - ZUMA。

题意

题意：给定一个长度为$n$的$01$串$s$与得分数组$a$，每次可以从$s$中删除任意子串（子串中所有字符必须相同），可以获得$a[子串长度]$的得分，求删除完$s$的最大得分。

数据范围：$1\leqslant n\leqslant 100$。

分析

首先观察题目，可以通过经验得到这道题是区间$dp$。

尝试设二维$dp$数组$f[l][r]$，代表删除区间$[l,r]$的最大得分，答案便是$f[1][n]$。

但是这个转移不好写（至少我不会写），而且加上数据范围很小，因此两维应该是不够的。

按照SP6340 ZUMA - ZUMA的经验，我们尝试设三维$dp$数组$f[l][r][k]$指删除区间前的$k$个与$l$颜色相同的数与区间$[l,r]$的最大得分，这样转移就很显然了：

1. 可以将前面附加的数与第$l$个数一起删除，就可以从$f[l+1][r][0]$转移来，也就是f[l][r][k]=min(f[l][r][k],f[l+1][r][0]+a[k+1]);
2. 枚举所有与区间$[l,r]$第一个数相同的断点$p$，这样可以先删除区间$l+1,p-1$，然后删除前面附加的数$+$第$l$个数$+$区间$[p,r]$，也就是f[l][r][k]=min(f[l][r][k],f[l+1][p-1]+f[p][r][k+1]);

然后就是区间$dp$的常规做法了。

代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=105;
int i,j,k,m,n,p,len;
int a[maxn],f[maxn][maxn][maxn];
string s;
int main(){
    scanf("%d",&n);
    cin>>s;
    s=" "+s;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=2;i<=n;i++)
        for(j=1;j<i;j++)
            a[i]=max(a[i],a[j]+a[i-j]);
    for(len=1;len<=n;len++)
        for(i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(k=0;k<=n;k++){
                f[i][j][k]=max(f[i][j][k],f[i+1][j][0]+a[k+1]);
                for(p=i+1;p<=j;p++)
                    if(s[i]==s[p])
                        f[i][j][k]=max(f[i][j][k],f[i+1][p-1][0]+f[p][j][k+1]);
            }
        }
    printf("%d\n",f[1][n][0]);
    return 0;
}