uva 1351 String Compression(字元串區間dp)

本文出自   http://blog.csdn.net/shuangde800

題目來源： 點選打開連結

題目大意

給一個字元串，可以把連續相同的部分進行縮寫成k(S)的形式，S是一個字元串，k表示有連續相同的S

例如，abgogogogo，可以縮寫成ab4(go). 還可以嵌套縮寫，比如

“nowletsgogogoletsgogogo”， 縮寫成“now2(lets3(go))”

思路

一道區間dp，但是這題并不好想

f(i, j)表示字元串的i~j位的最小位數

那麼

f(i, j) = min{

                  min{ f(i,k)+f(k+1, j), i<=k<j }，

                  min{ digitNum(k)+f[l][l+k-1]+2, 如果字元串可以由前k個字元串重複組成的 }

                }

digitNum(k)表示數字k的位數

判斷區間（i, j）是否有由連續ｋ個組成的字元串連續組成的，直接用Ｏ(n)的時間判斷

代碼

/**==========================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source：uva-1351 String Compression
 *   @type:  區間dp
 *   @author: shuangde
 *   @blog: blog.csdn.net/shuangde800
 *   @email: [email protected]
 *===========================================*/
#include
   
    
#include
    
     
#include
     
      
#include
      
       
#include
       
         #include
        
          #include
         
           using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const double PI = acos(-1.0); const int MAXN = 210; char str[MAXN]; int f[MAXN][MAXN], len; // 判斷字元串區間[l,r]之否由[l,l+k-1]字串連續組成的 bool check(int l, int r, int k){ int len = r-l+1; int i = 0; while(i < k){ for(int p=1; l+p*k+i<=r; ++p){ if(str[l+i] != str[l+p*k+i]) return false; } ++i; } return true; } // 計算數字ｘ有幾位 inline int digitNum(int x){ int cnt = 0; while(x > 0){ ++cnt; x /= 10; } return cnt; } int main(){ int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%s", str+1); len = strlen(str+1); for(int i = 1; i <= len; ++i) f[i][i] = 1; for(int d = 2; d <= len; ++d) { for(int l = 1; l+d-1 <= len; ++l) { int r = l + d - 1; f[l][r] = INF; int& ret = f[l][r]; for(int k=l; k