NC25229. 神秘的字符串
描述
某华大学的漂亮小姐姐Anna得到了一个字符串s，她很好奇的看着这个字符串，然而，这个字符串有点害羞。这下，Anna更好奇了。
在Anna好奇的大眼睛注视下，字符串s偏着脸说出了它的秘密。
“我们每一个字符串都有它的价值。嗯，这个价值有它衡量的标准。我是一个只含有0，1的字符串，我的衡量标准是可以删除一段连续的0或者1，删除后，剩下的拼接到一起（举个栗子，011110，如果我删除第3、4位连续的两个1后，就剩下0110），如果我删除的长度为a，我可以得到va的价值。我可以删除任意次数，直到全部删完。现在，我的秘密就是所有操作后得到的价值的总和的最大值。你，知道我的秘密是多少吗？”
“好像有点难啊？”Anna歪着脑袋说。
输入描述
输入包括三行。第一行包括一个整数n（表示这个字符串的长度）。第二行是这个字符串。（保证只由0，1组成且只有n个字符）。第三行，包括n个整数v1,v2,…,vi,vi+1,…,vn。vi表示删除i位连续的字符会得到vi大小的价值。（0<n<=100，0<vi<=1000000000）。
输出描述
每组测试数据输出一行，为可以得到的最大价值。
示例1
输入:
7 1101001 3 4 9 100 1 2 3
输出:
109
示例2
输入:
5 10101 3 10 15 15 15
输出:
23
示例3
输入:
5 11111 100 1 1 1 1
输出:
500
说明:
对于样列三，我们没有必要删除连续两位或者三位，四位，五位的1（虽然我们可以这么做）。因为我将五个1分开删除我们就可以得到最大的价值。C++(g++ 7.5.0) 解法, 执行用时: 57ms, 内存消耗: 9500K, 提交时间: 2023-03-29 10:07:22
#include <iostream>
#include <cstring>
using namespace std;
const int N=105;
long long dp[N][N][N];
int a[N];
char s[N];
long long dfs(int l, int r, int k)
{
if(l>r) return 0;
if(~dp[l][r][k])
return dp[l][r][k];
dp[l][r][k]=dfs(l, r-1, 1)+a[k];
for(int i=r-1; i>=l; i--)
if(s[r]==s[i])
dp[l][r][k]=max(dp[l][r][k], dfs(l, i, k+1)+dfs(i+1, r-1, 1));
return dp[l][r][k];
}
int main()
{
int n; scanf("%d", &n);
scanf("%s", s+1);
memset(dp,-1,sizeof(dp));
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
cout << dfs(1, n, 1) << '\n';
return 0;
}
C++14(g++5.4) 解法, 执行用时: 68ms, 内存消耗: 10980K, 提交时间: 2019-04-21 10:49:44
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
using namespace std;
const int N=110;
int n,a[N]; ll f[N][N][N]; char s[N];
ll dfs(int l,int r,int k){
if (l>r) return 0;
if (~f[l][r][k]) return f[l][r][k];
ll res=a[k]+dfs(l+1,r,1);
rep (i,l+1,r) if (s[i]==s[l]) res=max(res,dfs(l+1,i-1,1)+dfs(i,r,k+1));
return f[l][r][k]=res;
}
int main(){
scanf("%d%s",&n,s+1);
rep (i,1,n) scanf("%d",&a[i]);
memset(f,-1,sizeof(f));
cout<<dfs(1,n,1)<<'\n';
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 9568K, 提交时间: 2019-04-21 17:10:42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int val[105],n;
char s[105];
ll f[105][105][105];
ll dfs(int l,int r,int k)
{
if(l>r)
return 0;
if(f[l][r][k]!=-1)
return f[l][r][k];
ll ans=val[k]+dfs(l+1,r,1);
for(int i=l+1;i<=r;i++)
if(s[i]==s[l])
ans=max(ans,dfs(l+1,i-1,1)+dfs(i,r,k+1));
return f[l][r][k]=ans;
}
int main()
{
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
memset(f,-1,sizeof(f));
printf("%lld\n",dfs(1,n,1));
}