前面自己写的动态方程转移出现了问题,还是没有考虑周全.
AC代码:
#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; /* 题意:给定了一个字符串,问这个字符串,这个字符串是由a,b,c,...,a+N-1的字符集组成的 现在问使用使得该串成为一个回文串的最少花费是多少. 花费的定义如下: 对于每一个字符,给出添加这个字符和删除这个字符分别需要花费多少. 添加和删除 可以再任何位置进行. 解法:前面的写法是错误的,因为状态中的dp[i][j]表示从i到j只能够去删除和改变字符, 并没有涉及到添加字符进去的操作,也就是说dp[i][j]取得最优值的时候长度可能 是大于j-i+1的. 说明前面开设的状态理解有问题, 也就导致转移方程不能够很好的解决问题 重新定义dp[i][j]表示可能含有[i,j]子串的回文串的最少开销是多少. 那么就有动态方程: dp[i][j] = min(dp[i+1][j]+cost[i], dp[i][j-1]+cost[j]); 上述方程生动的描述了对边界的两个字符的选择过程,cost[i]本身就是经过选择 而来的值,其表示是删除一个i节点还是在右边增加一个i节点. 加上后面的一部分 合起来就是对左右两边字符的考虑. if (str[i] == str[j])的话,那么就还有一种选择了 dp[i][j] = min(dp[i][j], dp[i-1][j-1]); */ int N, M, dp[2005][2005]; int cost[30]; char str[2005]; int DP() { for (int i = 1; i < M; ++i) { // 枚举区间左右端点的差值 for (int j = 1; j+i <= M; ++j) { int a = j, b = j + i, ll = str[a]-'a', rr = str[b]-'a'; dp[a][b] = min(dp[a+1][b] + cost[ll], dp[a][b-1] + cost[rr]); if (ll == rr) dp[a][b] = min(dp[a][b], dp[a+1][b-1]); // 如果端点差值为1的话,dp[a+1][b-1]会使得区间无意义,当时这个无意义的值刚好为0 } } return dp[1][M]; } int main() { char s[5]; int a, b; while (scanf("%d %d", &N, &M) == 2) { scanf("%s", str+1); for (int i = 1; i <= N; ++i) { scanf("%s %d %d", s, &a, &b); cost[s[0]-'a'] = min(a, b); // 这里直接求出这个最小值,因为对每一个点有两种选择,一是删去,而是添加一个 } printf("%d\n", DP()); } return 0; }
WA代码:
View Code
#include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; /* 题意:给定了一个字符串,问这个字符串,这个字符串是由a,b,c,...,a+N-1的字符集组成的 现在问使用使得该串成为一个回文串的最少花费是多少. 花费的定义如下: 对于每一个字符,给出添加这个字符和删除这个字符分别需要花费多少. 添加和删除 可以再任何位置进行. 解法:设定状态dp[i][j]表示[i,j]这段区间为回文串的最少花费是多少. 那么有dp方程: dp[i][j] = min(dp[i-1][j-1]+X, dp[i-1][j]+X, dp[i][j-1]+X), 第一个表示左右 边界都要,第二个和第三个分别表示左边和右边的一个删除 最后的回文串一定不会是两端都添加字符, 否则同时在两端删除新添加的字符一定也 是最优解 */ int N, M, dp[4005][4005]; char str[4005]; struct Node { int afee, dfee; }e[30]; int DP() { int lim = M << 1; // 最多可以再添加一个M长的字符串在后面 memset(dp, 0x3f, sizeof (dp));// 保证非法状态dp值为无穷大 for (int i = 1; i <= lim; ++i) { // 初始化只有一个字符的串 dp[i][i] = 0; // 该位置已有字符,最好的办法就是什么都不做,形成一个单字符回文串 } for (int i = 1; i < lim; ++i) { // 初始化只有两个字符的串 if (str[i] == str[i+1]) dp[i][i+1] = 0; else { int Min = INF; Min = min(Min, e[str[i]-'a'].dfee); Min = min(Min, e[str[i+1]-'a'].dfee); dp[i][i+1] = Min; } } // 根据dp[i][j]的含义,显然i <= j的情况下,dp值才有意义 for (int i = 2; i < lim; ++i) { // 枚举区间左右端点的差值 for (int j = 1; j + i <= lim; ++j) { int a = j, b = j + i; // a, b 分别表示左右边界 int Min = INF, ll = str[a]-'a', rr = str[b]-'a'; Min = min(Min, dp[a+1][b] + e[ll].dfee); // 删除a号位置 Min = min(Min, dp[a][b-1] + e[rr].dfee); // 删除b号位置 if (ll == rr) { Min = min(Min, dp[a+1][b-1]); } else { Min = min(Min, dp[a+1][b-1] + e[ll].dfee + e[rr].dfee); // 删除左右两个 Min = min(Min, dp[a+1][b-1] + e[rr].dfee + e[ll].afee); // 将右边改为左边字符 Min = min(Min, dp[a+1][b-1] + e[ll].dfee + e[rr].afee); // 将左边改为右边字符 } dp[a][b] = Min; } } return dp[1][lim]; } void srev(char *s) { int len = strlen(s); for (int i = 0, j = len-1; i < j; ++i, --j) { char t = s[i]; s[i] = s[j]; s[j] = t; } } int main() { char s[5]; int a, b, ret; while (scanf("%d %d", &N, &M) == 2) { ret = INF; memset(str, 'a'+26, sizeof (str)); // 全部赋值为26,这样就假设后面补了一个字母,这个字母的代价添加和删除都是0 scanf("%s", str+1); // 从第一位开始录入 str[M+1] = 'a'+26; // 人为把'\0'赋值为26 for (int i = 0; i < N; ++i) { scanf("%s %d %d", s, &a, &b); e[s[0]-'a'].afee = a; e[s[0]-'a'].dfee = b; // 将添加和删除字符的代价记录起来 } ret = min(ret, DP()); // 都假设从后面添加字符 str[M+1] = '\0'; srev(str+1); str[M+1] = 'a'+26; ret = min(ret, DP()); // 通过翻转也就等同与从前面添加字符 printf("%d\n", ret); } return 0; }