hdu 1513 Palindrome<最长公共子序列>

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513

最长公共子序列模版题。

View Code

 1 #include <cstdio>
 2  #include<iostream>
 3  #include<string.h>
 4  using namespace std;
 5  char cc[5001];
 6  int dp[2][5001];
 7  int n;
 8  inline int Min(int x,int y)
 9  {
10      return x>y?y:x;
11  }
12  int main()
13  {
14      while(scanf("%d",&n)!=EOF){
15          scanf("%s",cc+1);
16          memset(dp,0,sizeof(dp));
17          for(int i=n-1;i>=1;i--)
18              for(int j=i+1;j<=n;j++){
19                  if(cc[i]==cc[j])
20                      dp[i%2][j]=dp[(i+1)%2][j-1];
21                  else
22                      dp[i%2][j]=1+Min(dp[(i+1)%2][j],dp[i%2][j-1]);
23              }
24              printf("%d\n",dp[1][n]);
25      }
26      return 0;
27  }