Codeforces 1107E Vasya and Binary String 记忆化 dp

发表于 2019-02-02 分类于算法阅读次数： 59 本文字数： 2.3k 阅读时长 ≈ 2 分钟

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 \leq n \leq 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 \leq a_{i} \leq 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:

题目链接

题解:

你有一个长为 n 的 01 串，每次可以消去长度为 $l e n $ 的连续相同字符，收益为 $a_{l e n} $ , 求消去整个串的收益最大值

记忆化 dp

设 $d p [0, 1] [l] [r] [c n t]$ 代表把 $l$ 到 $r$ 删除到只剩下 $c n t$ 个 0 或 1 的最大收益， $a n s [l] [r]$ 代表把 $l$ 到 $r$ 删完的最大收益

转移方程为 $a n s [l] [r] = {max}_{c n t = 1}^{r - l + 1} (a [c n t] + d p [0, 1] [l] [r] [c n t])$ , $d p [c] [l] [r] [c n t] = {max}_{s [i] = c, i = l}^{r - 1} (a n s [l] [i - 1] + d p [c] [i + 1] [r] [c n t - 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;
}