題目鏈接：?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\n", dp[n][m] );}return 0; } View Code

　　思考：狀態轉移時， 要注意和狀態轉移有關的變量有哪幾個， 是否能夠從原條件中預處理出來， 如果能夠預處理出來就去做， 否則就換狀態

轉載于:https://www.cnblogs.com/FriskyPuppy/p/7323400.html

總結

以上是生活随笔為你收集整理的UVA 1625 Color Length DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。