Codeforces 1120C Compress String(DP)

2019/04/07 12:59
阅读数 5

题意:给你一个字符串,有2种消除方式:1:消除一个单独的字母,代价为a。2:s[j]到s[k]是s[1]到s[j - 1]的子串,那么s[j]到s[k]可以消除,代价为b,问最小的代价。

思路:官方题解说的很明白了。

代码:

#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 5010;
int dp[maxn];
int v[maxn][maxn];
int Next[maxn];
char s[maxn];
int n, a, b;
int main() {
//	freopen("inupt.txt", "r", stdin);
	scanf("%d%d%d", &n, &a, &b);
	scanf("%s",s + 1);
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++) {
			if(s[i] == s[j]) {
				v[i][j] = v[i - 1][j - 1] + 1;
			}
		}
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + a;
		for (int j = 1; j < i; j++) {
			int t = min(i - j, v[j][i]);
			if(t) {
				dp[i] = min(dp[i], dp[i - t] + b);
			} 
		}
	}	
	printf("%d\n", dp[n]);
}

  

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部