Vasya and Binary String(来自codeforces

发布时间：2020-12-14 04:23:05 所属栏目：大数据来源：网络整理

导读：题目大意：给定一个0/1字符串，每次你可以将此字符串中一段连续的任意长度的0/1子串消除掉，注意每次消除的子串中只能有0或者1一种字符，消除掉一串长度为i的0/1字符串会得到a[i]的收益，问将这个字符串完全消除的最大收益 Examples Input ? ? ?7? ? ? ?110

题目大意：

给定一个0/1字符串，每次你可以将此字符串中一段连续的任意长度的0/1子串消除掉，注意每次消除的子串中只能有0或者1一种字符，消除掉一串长度为i的0/1字符串会得到a[i]的收益，问将这个字符串完全消除的最大收益

Examples

Input

? ? ?7?

? ? ?1101001

? ? ?3 4 9 100 1 2 3

Output

Input

? ? 5

? ?10101?

? ? 3 10 15 15 15

Output

第一个样例是1101001 →→ 111001 →→ 11101 →→ 1111 →→ ? .

第二个样例是10101 →→ 1001 →→ 11 →→ ? .

区间dp+记忆化搜索

 #include<bits/stdc++.h>
using namespace std;
long long n,i;
long long s[105];
long long a[105];
long long f[105][105][55];
long long dfs(long long l,long long r,long long x)
{
	long long ans,j;
    if(l>r)return 0;
    if(f[l][r][x]!=-1)return f[l][r][x];
    if(l==r)return f[l][r][x]=a[x];
    
    ans=a[x]+dfs(l+1,r,1);
    for(j=l;++j<=r;)
	  if(s[j]==s[l])ans=max(ans,dfs(l+1,j-1,1)+dfs(j,x+1));
    return f[l][r][x]=ans;
} 
int main()
{
    for(scanf("%lld",&n),memset(f,-1,sizeof(f)),i=0;++i<=n;)scanf("%1lld",&s[i]);
    for(i=0;++i<=n;)scanf("%d",&a[i]);
	 
    printf("%lld",dfs(1,n,1));
    return 0;
}

　代码很简单（第一次在博客园写博客，有什么不足，请说明~~）

谢谢观赏~~

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!