题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4500
题目描述： 两个字符串 ，组成一个新的字符串， 每次只能从其中一个的开头选一个加到新的尾， 问l(i)的最小值
解题思路： dp(i, j) 表示从第一个字符串中取i 个， 第二个字符串中取j个时的最优方案， 我们创建数组c 表示从第一个字符串中取i 个， 第二个字符串中取j个时开始还没有结束的字符的数量， 这样状态转移方程就可以写成： dp(i,j) = min(dp(i-1,j)+c[i-1,j], dp(i, j-1)+c[i,j-1]) 我们每做一次状态转移就更新一次c数组
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 typedef long long LL; using namespace std; const int maxn = 5000+5; int dp[maxn][maxn]; // dp(i,j) p中取i个, q中取j个的最小代价 char p[maxn]; char q[maxn]; int c[maxn][maxn]; // c(i,j) p中取i个, q中取j个已经开始还没有结束字符的个数 int sp[30], sq[30], ep[30], eq[30]; const int INF = 0x3fffffff; int main() { int t; scanf( "%d", &t ); while( t-- ) { // scanf( "%s", p+1); // scanf( "%s", q+1); scanf("%s%s", p + 1, q + 1); int n = (int)strlen(p+1); int m = (int)strlen(q+1); memset(c, 0, sizeof(c)); memset(dp, 0, sizeof(dp)); for( int i = 1; i <= n; i++ ) p[i] -= 65; for( int j = 1; j <= m; j++ ) q[j] -= 65; for( int i = 0; i < 26; i++ ) { sp[i] = sq[i] = INF; ep[i] = eq[i] = 0; } for( int i = 1; i <= n; i++ ) { sp[p[i]] = min( sp[p[i]], i ); ep[p[i]] = i; } for( int i = 1; i <= m; i++ ) { sq[q[i]] = min( sq[q[i]], i ); eq[q[i]] = i; } for( int i = 0; i <= n; i++ ) { for( int j = 0; j <= m; j++ ) { if( !i && !j ) continue; int v1, v2; v1 = v2 = INF; if( i ) v1 = dp[i-1][j] + c[i-1][j]; if( j ) v2 = dp[i][j-1] + c[i][j-1]; dp[i][j] = min( v1, v2 ); if( i ) { c[i][j] = c[i-1][j]; // if( sp[p[i]] == i && (ep[p[i]] > i || eq[p[i]] > j ) ) c[i][j]++; // if( ep[p[i]] == i && eq[p[i]] <= j ) c[i][j]--; if (sp[p[i]] == i && sq[p[i]] > j) c[i][j]++; if (ep[p[i]] == i && eq[p[i]] <= j) c[i][j]--; } else if( j ) { c[i][j] = c[i][j-1]; // if( sq[q[j]] == j && (eq[q[j]] > j || ep[q[j]] > i ) ) c[i][j]++; // if( eq[q[j]] == j && ep[q[j]] <= i ) c[i][j]--; if (sq[q[j]] == j && sp[q[j]] > i) c[i][j]++; if (eq[q[j]] == j && ep[q[j]] <= i) c[i][j]--; } } } printf( "%d ", dp[n][m] ); } return 0; }
思考：状态转移时， 要注意和状态转移有关的变量有哪几个， 是否能够从原条件中预处理出来， 如果能够预处理出来就去做， 否则就换状态