首页 > 代码库 > HDU 4745 Two Rabbits（最长回文子序列）
HDU 4745 Two Rabbits（最长回文子序列）
http://acm.hdu.edu.cn/showproblem.php?pid=4745
题意：
有一个环，现在有两只兔子各从一个点开始起跳，一个沿顺时针，另一个沿逆时针，只能在一圈之内跳，并且每次所在的点的大小必须相同，问最多能经过 几个点。
思路：
环状的话可以先倍增改成链。
这道题目的话就是求最长回文子串，它的求法是这样的：
设字符串为str，长度为n，p[i][j]表示第i到第j个字符间的子序列的个数（i<=j），则：
状态初始条件：dp[i][i]=1 （i=0：n-1）
状态转移方程：dp[i][j]=dp[i+1][j-1] + 2 if（str[i]==str[j]）
dp[i][j]=max(dp[i+1][j],dp[i][j-1]) if （str[i]!=str[j]）
最后找最大值的时候，除了找区间长度为n的，还要找区间长度为n-1的，此时的情况是两只兔子从同一个起点出发。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef long long ull;15 typedef pair<int,int> pll;16 const int INF = 0x3f3f3f3f;17 const int maxn = 2000 + 5;18 19 int n;20 int a[maxn];21 int d[maxn][maxn];22 23 int main()24 {25 freopen("in.txt","r",stdin);26 while(~scanf("%d",&n) && n)27 {28 for(int i=1;i<=n;i++)29 {30 scanf("%d",&a[i]);31 a[i+n]=a[i];32 d[i][i]=d[i+n][i+n]=1;33 }34 35 for(int r=2;r<=n;r++)36 {37 for(int i=1;i+r-1<=2*n;i++)38 {39 int j=i+r-1;40 if(a[i]!=a[j]) d[i][j]=max(d[i+1][j],d[i][j-1]);41 else if(a[i]==a[j]) d[i][j]=d[i+1][j-1]+2;42 }43 }44 45 int ans=0;46 for(int i=1;i<=n;i++)47 {48 ans=max(ans,d[i][i+n-1]);49 ans=max(ans,d[i][i+n-2]+1); //两只兔子从同一个起点出发50 }51 printf("%d\n",ans);52 }53 return 0;54 }
HDU 4745 Two Rabbits（最长回文子序列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。