Codeforces 1107 E - Vasya and Binary String
发布时间:2020-12-14 05:13:35 所属栏目:大数据 来源:网络整理
导读:E - Vasya and Binary String 思路:区间dp + 记忆化搜索 转移方程看上一篇博客。 代码: #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include bits/stdc++.h using namespace std; #define fi first #define se second #def
E - Vasya and Binary String 思路:区间dp + 记忆化搜索 转移方程看上一篇博客。 代码: #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define y1 y11 #define pi acos(-1.0) #define LL long long //#define mp make_pair #define DEBUG #define pb push_back #define ls rt<<1,l,m #define rs rt<<1|1,m+1,r #define ULL unsigned LL #define pll pair<LL,LL> #define pli pair<LL,int> #define pii pair<int,int> #define piii pair<pii,int> #define pdd pair<long double,long double> #define mem(a,b) memset(a,b,sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt","r",stdin);freopen("out.txt","w",stout); //head const int N = 105; LL dp[N][N][N]; string s; int a[N]; LL dfs(int l,int r,int k) { if(l > r) return 0; if(l == r) return a[k+1]; if(~dp[l][r][k]) return dp[l][r][k]; dp[l][r][k] = dfs(l,r-1,0) + a[k+1]; for (int i = l; i < r; i++) { if(s[i] == s[r]) { dp[l][r][k] = max(dp[l][r][k],dfs(i+1,0) + dfs(l,i,k+1)); } } return dp[l][r][k]; } int main() { fio; int n; cin >> n; cin >> s; for (int i = 1; i <= n; ++i) cin >> a[i]; mem(dp,-1); cout << dfs(0,n-1,0) << endl; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |