题意
给一串01串，对该串进行若干次操作，直到串为空
操作为：选择一段连续的0或者1,删除它，拼接前后两部分成为新串，得到价值为a[删除的长度]（a为给定的数组）
思路
一个非常规的DP
考虑题目所给的操作，我们从中删除一段，再把前后拼接起来，如何设置状态？记录下断点的位置？不行，那样我们可能在其中插入很多断点，并且不便于转移
(...111000111...)
如果我们仅仅研究中间的子串(111000111)
我们删除中间的0,形成(111111)
再删除中间的1,这样我们其实可以看做原串是(000underline{111}111)
也就是前面的1和后面的1其实是捆在一起的，这样按原来的操作，答案不会改变
设置状态：(dp[i][j][k]) 表示删除从i到j的子串，该子串前面捆绑了(k-1)个与(s[i])相同的字符，能得到的最大价值
这样的话，考虑转移方式：
-
我们直接删除前面(k)个相等的字符，(dp[i][j][k] = a[k] + dp[i+1][j][1])，因为捆绑的全消耗掉了所以后半部分是(K = 1)
-
我们从中删除一段，再把前后粘贴起来，这样的话，也就是上面的情况，我们需要把前面的和后面的捆绑起来，所以必须满足从中找到一个点(mid > i,s[i] = s[mid])，这样的话(dp[i][j][k] = dp[i+1][mid-1][1] + dp[mid][j][k+1])
看这个式子，我们只捆绑的是第一个字符，因为我们可以多次进行这样的操作，使得捆绑的是任意的（这里不需要我们自己去构造，而是在求解过程中自然构造的）
所以最后的答案是(dp[1][n][1])
由于这个转移比较骚，我们可以采用记忆化搜索
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[105];
ll a[105];
ll dp[105][105][105];
ll DP(int be,int en,int pre) {
if(be > en) return 0;
if(dp[be][en][pre]) return dp[be][en][pre];
if(be == en) return dp[be][en][pre] = a[pre];
ll ans = a[pre] + DP(be+1,en,1);
for(int mid = be+1;mid <= en;mid++) {
if(s[mid] == s[be])
ans = max(ans,DP(be+1,mid-1,1) + DP(mid,en,pre+1));
}
return dp[be][en][pre] = ans;
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
cin>>s+1;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<DP(1,n,1)<<endl;
}