Codeforces1107E Vasya and Binary String 记忆化dp
Codeforces1107E 记忆化dp
E. Vasya and Binary String
Description:
Vasya has a string \(s\) of length \(n\) consisting only of digits 0 and 1. Also he has an array \(a\) of length \(n\).
Vasya performs the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue together the remaining parts (any of them can be empty). For example, if he erases substring 111 from string 111110 he will get the string 110. Vasya gets \(a_x\) points for erasing substring of length \(x\).
Vasya wants to maximize his total points, so help him with this!
Input:
The first line contains one integer \(n\) (\(1 \le n \le 100\)) — the length of string \(s\).
The second line contains string \(s\), consisting only of digits 0 and 1.
The third line contains \(n\) integers \(a_1, a_2, \dots a_n\) (\(1 \le a_i \le 10^9\)), where \(a_i\) is the number of points for erasing the substring of length \(i\).
Output
Print one integer — the maximum total points Vasya can get.
Sample Input:
7
1101001
3 4 9 100 1 2 3
Sample Output:
109
Sample Input:
5
10101
3 10 15 15 15
Sample Output:
23
题目链接
题解:
你有一个长为n的01串,每次可以消去长度为\(len\)的连续相同字符,收益为\(a_{len}\),求消去整个串的收益最大值
记忆化dp
设\(dp[0,1][l][r][cnt]\)代表把\(l\)到\(r\)删除到只剩下\(cnt\)个0或1的最大收益,\(ans[l][r]\)代表把\(l\)到\(r\)删完的最大收益
转移方程为\(ans[l][r] = \max_{cnt = 1}^{r-l+1}(a[cnt] + dp[0,1][l][r][cnt])\),\(dp[c][l][r][cnt] = \max_{s[i] = c, i = l}^{r - 1}(ans[l][i-1] + dp[c][i+1][r][cnt-1])\),cnt=1时特判一下
状态数为\(O(n^3)\),转移为\(O(n)\),总复杂度为\(O(n^4)\)
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 102;
long long dp[2][N][N][N], ans[N][N];
int n, a[N];
char s[N];
long long calcdp(int c, int l, int r, int cnt);
long long calcans(int l, int r) {
if(l > r) return 0;
long long &res = ans[l][r];
if(res != -1) return res;
res = 0;
for(int cnt = 1; cnt <= r - l + 1; ++cnt) {
res = max(res, a[cnt] + calcdp(0, l, r, cnt));
res = max(res, a[cnt] + calcdp(1, l, r, cnt));
}
return res;
}
long long calcdp(int c, int l, int r, int cnt) {
if(cnt == 0) return dp[c][l][r][cnt] = calcans(l, r);
long long &res = dp[c][l][r][cnt];
if(res != -1) return res;
res = -1e10;
for(int i = l; i < r; ++i) {
if(s[i] - '0' == c)
res = max(res, calcans(l, i - 1) + calcdp(c, i + 1, r, cnt - 1));
}
if(cnt == 1 && s[r] - '0' == c)
res = max(res, calcans(l, r - 1));
return res;
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
memset(dp, -1, sizeof(dp));
memset(ans, -1, sizeof(ans));
int t, a, b, c, d;
printf("%lld\n", calcans(1, n));
return 0;
}
最新文章
- JavaScript中的slice,splice,substr,substring,split的区别
- 【转】Checkpoint--与lazy writer区别
- Git工作流总结
- MVC模型
- Ubuntu 14.04/14.10下安装VMware Workstation 11图文教程
- Jpush教材
- 根据标点符号分行,StringBuilder的使用;将字符串的每个字符颠倒输出,Reverse的使用
- netty&mdash;&mdash;私有协议栈开发案例
- jquery如此强大,为什么还要写原生呢?
- Jmeter性能测试之Monitor监控(SSHMon Samples Collector)
- os模块(操作系统)
- oracle错误(ORA:12154 ORA:01034 和 ORA:27101 ORA-18008 ORA-01081)
- android java 字符串正则表达式 分离特殊字符串
- 源发行版 1.8 需要目标发行版 1.8以及usage of api documented as @since 1.8+
- elasticsearch数据过期删除处理
- windows下mongodb基础玩法系列一介绍与安装
- DllPlugin、DllReferencePlugin 可以提取的第三方库列表
- November 8th 2016 Week 46th Tuesday
- position:fixed部分版本的浏览器不支持
- JavaScript中文拼音排序函数