POJ 1159 回文LCS滚动数组优化-白红宇

POJ 1159 回文LCS滚动数组优化

阅读量：4356 次

发布时间：2019-06-07

本文共 1274 字，大约阅读时间需要 4 分钟。

详细解题报告可以看这个PPT

这题如果是直接开int 5000 * 5000 的空间肯定会MLE，优化方法是采用滚动数组。

原LCS转移方程：

dp[i][j] = dp[i - 1][j] + dp[i][j  -1]

因为 dp[i][j] 只依赖于 dp[i - 1][j] 和 dp[i][j - 1]

所以可以采用滚动数组如下：

dp[i % 2][j] = dp[(i - 1) % 2][j] + dp[i % 2][j - 1]

可以实现节省空间的方法

答案存储在 dp[n % 2][n] 中

source code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 500;int dp[2][5005];int main(){ int i, j, t, k, n, m; string str1, str2; while(EOF != scanf("%d",&n)){ cin >> str1; str2 = str1; reverse(str1.begin(), str1.end()); memset(dp, 0, sizeof(dp)); for(i = 1; i <= n; ++i){ for(j = 1; j <= n; ++j){ if(str1[i - 1] == str2[j - 1]){ dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - 1] + 1); } else{ dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]); } } } cout << n - dp[n % 2][n] << endl; //answer = X.length() - LCS(X, Y) } return 0;}