比赛的时候又被垃圾题艹翻了啊。
这个题显然是区间dp
考虑怎么转移。
类似消除方块和ZYB玩字符串那样的一个DP。
可以从左到右依次考虑消除。
dp[l][r][k][flag]表示区间l,r左边粘着k个flag。
转移方式：
1.考虑强行去继续黏上下一个字符并使k+1。
2.考虑把一段跳过去，让被跳过的这一段自行不与外界产生关系被消除，然后再去消除后面的。
3.直接消除当前粘着的一段，并获得收益。
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 110
#define L 100
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline ll read()
{
char ch=0;
ll x=0,flag=1;
while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*flag;
}
char s[N];
ll a[N],f[N],dp[N][N][N][2];
ll dfs(ll l,ll r,ll k,ll flag)
{
if(l>r)return a[k];
if(dp[l][r][k][flag]!=-1)return dp[l][r][k][flag];
if(!k||(k&&f[l]==flag))
dp[l][r][k][flag]=max(dp[l][r][k][flag],dfs(l+1,r,k+1,f[l]));
for(ll i=l;i<=r;i++)
dp[l][r][k][flag]=max(dp[l][r][k][flag],dfs(l,i,0,0)+dfs(i+1,r,k,flag));
for(ll i=1;i<=k;i++)
dp[l][r][k][flag]=max(dp[l][r][k][flag],dfs(l,r,k-i,flag)+a[i]);
return dp[l][r][k][flag];
}
int main()
{
ll n=read();
scanf("%s",s+1);
for(ll i=1;i<=n;i++)a[i]=read(),f[i]=s[i]-'0';
memset(dp,-1,sizeof(dp));
printf("%lld",dfs(1,n,0,0));
return 0;
}