CF1107E-solution

· · 题解

\text{Description}

洛谷 link

CFlink

简要题意：

给定 01 串 s，每次从 s 中删除一个所有字符都相同的字段并获得 a_k（k 为字段长度）的分数，问将 s 删成空串能获得的最大分数。

\text{Solution}

歪解警告，一开始想区间 dp 没想到什么好的做法，于是突发奇想想到了下面这个做法。

显然可以先 O(n^2) 处理 a 数组，处理成单增。

设 f_s 表示将字符串 s 删成空串的最大分数，用 umap 存储，用记忆化搜索转移。

如果暴力去转移的话时间复杂度肯定是错误的，但是我们将 a 处理成单增的了，所以将相同的字符尽可能放在一起删一定是更优的。

所以我们令当前字符串的第一个字符为基准字符，将开头连续的基准字符一次性处理一定是更优的。

接着遍历后面的字符，每当遇到与基准字符相同的字符，则考虑将这之间的字符抠出来，将这一段先删掉，然后其他的拼起来再处理。

语文水平不是很好，大家可以按下面这个图理解。

整个字符串为 s，前面连续的一段子段为 A，中间抠掉的部分为 T，剩下的部分为 B。

那么 f_{A+B}+f_{T} 就是一种可能更新 f_s 的值（A+B 表示将 B 接在 A 后面）。

感谢 YK 大神证明了这个算法的复杂度：

具体实现可参考代码。 # $\text{Code} 
#include<bits/stdc++.h>
#define int long long
#define N 105
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
int n,a[N];
string s;
unordered_map<string,int>f;//用 umap 代替 map 可以有效提高程序效率
string sub(string s,int l,int r){
    string t="";
    for(int i=l;i<=r;++i) t+=s[i];
    return t;
}
int dfs(string s){
    if(s.size()<=1) return a[s.size()];
    if(f.count(s)) return f[s];
    int res=0,p=0,len=s.size();
    while(p<len && s[0]==s[p]) ++p;
    res=max(res,dfs(sub(s,p,len-1))+a[p]);
    for(int i=p;i<len;++i) if(s[i]==s[0]) res=max(res,dfs(sub(s,p,i-1))+dfs(sub(s,0,p-1)+sub(s,i,len-1)));
    return f[s]=res;
}
signed main(){
    n=read();cin>>s;
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=2;i<=n;++i) for(int j=1;j<=i;++j) a[i]=max(a[i],a[j]+a[i-j]);
    printf("%lld",dfs(s));
    return 0;
}