POJ - 1159 - Palindrome （LCS + 优化） - c++编程基础

TOP

POJ - 1159 - Palindrome （LCS + 优化）

2015-11-21 01:03:22 来源: 作者: 【大中小】浏览:2次

思路：一看题目思路很清晰，就是求出字符串s和倒转s后的字符串t的最长公共子序列，但是一看空间开销有点大，如果开int就会爆，5000*5000有100MB了，这里可以开short int，差不多正好可以过去，还有一种做法就是弄一个滚动数组，因为求LCS，根据状态转移方程可以知道，只需要前一行和当前行就行了，所以开个2*5005就OK了，具体看代码

AC代码①：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #define LL long long #define INF 0x7fffffff using namespace std; char s[5005]; char t[5005]; short int dp[5005][5005]; int main() { int N; cin >> N; scanf(%s, s + 1); for(int i = 1; i <= N; i ++) { t[N - i + 1] = s[i]; } t[N + 1] = ''; for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { if(s[i] == t[j]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } cout << N - dp[N][N] << endl; return 0; }

AC代码②：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #define LL long long #define INF 0x7fffffff using namespace std; int dp[2][5005]; char s[5005]; char t[5005]; int main() { int N; cin >> N; scanf(%s, s + 1); for(int i = 1; i <= N; i ++) { t[N + 1 - i] = s[i]; } t[N + 1] = ''; for(int i = 1; i <= N; i ++) { for(int j = 1; j <= N; j ++) { if(s[i] == t[j]) { 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; return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 题目1286 Necklace of Beads..	下一篇：HDU 5214 Movie (赛码"BestC..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: