首页 > 其他 > 详细

UVA11151

时间:2015-10-23 22:43:03      阅读:291      评论:0      收藏:0      [点我收藏+]
 1 /*
 2 题意: 选出多个字母组成回文,可以不连续,最长是多少。
 3 
 4 记忆化搜素.
 5 如果str[l]==str[r],dp[l][r]=dfs(l+1,r-1)+2, 
 6 否则  dp[l][r]=dfs(l+1,r), dfs(l,r-1));
 7 */ 
 8 
 9 #include<cstdio>
10 #include<algorithm>
11 #include<cstring>
12 #define MAX 1010
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 char str[MAX];
16 int dp[MAX][MAX];
17 int dfs(int l,int r)
18 {
19     if(dp[l][r]!=INF) return dp[l][r];
20     if(l==r ) return dp[l][r]=1;
21     if(l>r) return 0;
22     if(str[l]==str[r])     
23         dp[l][r]=dfs(l+1,r-1)+2;    
24     else    
25         dp[l][r]=max(dfs(l+1,r),dfs(l,r-1));    
26     return dp[l][r];
27 }
28 int main()
29 {
30     int t;
31     scanf("%d",&t);
32     getchar();
33     while(t--)
34     {
35         gets(str);
36         int l=strlen(str);
37         memset(dp,INF,sizeof(dp));
38         dfs(0,l-1);
39         printf("%d\n",dp[0][l-1]);
40     }
41     return 0;
42 }

 

UVA11151

原文:http://www.cnblogs.com/ember/p/4905802.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!