poj 3280 Cheapest Palindrome dp

缘起

区间dp 好题. poj 3280 Cheapest Palindrome

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
给你长度为m的字符串，其中有n种字符(就是小写字母)，每种字符都有两个值，分别是插入这个字符的代价，删除这
个字符的代价，
让你求将原先给出的那串字符通过加减这n种字符变成一个回文串的最小代价。注意，空字符串依旧被认为是符合
要求的.

【输入】
n和m
1 ≤ N ≤ 26
1 ≤ M ≤ 2,000
然后是长度为m的字符串
然后是n行，每行分别是每个字符的增加和删除的代价(0 ≤ cost ≤ 10,000)

【输出】
最小代价

【样例输入】
3 4
abcb
a 1000 1100
b 350 700
c 200 800

【样例输出】
900

【限制】
2s

【hint】
If we insert an "a" on the end to get "abcba", the cost would be 1000. If we delete 
the "a" on the beginning to get "bcb", the cost would be 1100. If we insert "bcb" at 
the begining of the string, the cost would be 350 + 200 + 350 = 900, which is the 
minimum.

dp好题.

本题注意范围1<=M<=2000, 所以O（M^2）的算法是可以被接受的.

令 dp[i][j] 等于使得 s[i,j] 区间成为回文串的最小代价（注意，只是使得，未必形成的回文串长度要是j-i+1）. 则dp[i][j] 能从哪些个状态转移而来呢? 从dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1] 三种状态转换而来. 如果是从dp[i+1][j]转换来的话, 则考虑s[i] 这个字符. 因为dp[i+1][j] 已经是回文了, 所以s[i]这个字符，我们要么删除它，要么新增它, 两种方法都可以使得[i,j] 变成回文. 所以

1
dp[i][j]需要在 dp[i+1][j]+add(s[i]) 和 dp[i+1][j]+del(s[i]) 中取小

如果是从 dp[i][j-1] 转换来的话，则考虑s[j] 这个字符. 同理，要么添加 s[j] 要么删除s[j] 就能使得s[i,..,j]成为回文

所以

1
dp[i][j]需要在 dp[i][j-1]+add(s[j]) 和 dp[i][j-1]+del(s[j]) 中取小

如果是从dp[i+1][j-1] 转换而来的话，则一定是s[i]=s[j], 如果不等的话，则一定是先转换为[i+1,j]或者 [i,j-1]再转换为[i,j]. 因为如果s[i]=s[j]的话，才可能不用删除任何一个字符（如果先转换为[i+1，j]或者[i,j-1]一定涉及字符的增删而造成费用）直接从[i+1,j-1]转换为[i,j]

所以

1
如果s[i]==s[j]， 则dp[i][j]要在dp[i+1][j-1]中取小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//#include "stdafx.h"

#include <stdio.h>
#include <stdarg.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m, a[26],d[26],dp[2005][2005]; // a是新增的代价，d是删除的代价
char s[2005];

int getmin(int n, ...) // n是参与取min的数的个数
{
	va_list args;
	va_start(args, n);
	int ans = ~0u>>1;
	for (int i = 0; i<n;i++)
	{
		ans = min(ans, va_arg(args, int));
	}
	va_end(args);
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%s", &n, &m, s);
	for (int i = 0,x,y; i<n;i++)
	{
		getchar(); // 吸收多余换行符
		char c = getchar();
		scanf("%d%d", &x, &y);
		a[c-'a'] = x, d[c-'a'] = y;
	}
	for (int i = 0; i<m-1;i++)
	{
		for (int j = i; j<m;j++)
		{
			dp[i][j] = i==j?0:0x3f3f3f3f;
		}
	} // dp的初始化, 注意, 不能memset(dp, 0x3f, sizeof(dp)) 因为dp[i][j]对于i>j的是0, 而不是0x3f3f3f3f
	for (int i = m-2; ~i; i--) // [i,j], 注意dp的次序, 因为i小的依赖大的, 则这种情况下i就要倒序, 否则就是正序
	{
		for (int j = i+1; j<m;j++)
		{
			if (s[i]==s[j]) dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
			dp[i][j] = getmin(5, dp[i][j], dp[i+1][j]+a[s[i]-'a'], dp[i+1][j]+d[s[i]-'a'], dp[i][j-1]+a[s[j]-'a'], dp[i][j-1]+d[s[j]-'a']); // 取四种情况最小
		}
	}
	printf("%d",dp[0][m-1]);
	return 0;
}

ac情况

Status Accepted
Time 63ms
Memory 13916kB
Length 1187
Lang C++
Submitted 2019-08-27 05:51:50
Shared
RemoteRunId 20805229