HDU 4745 （区间dp ，最长非连续回文子序列）

淡淡的烟草味﹌ 2024-02-17 19:34 7阅读 0赞

题意：输入一个序列，两只兔子分别顺时针、逆时针走，同一时刻它们到的石头上的数值要相同，最多只能走一圈，并且不能回到起点。。求走过的最多步数。

思路：dp求最长回文子序列。由于是一个环，所以起始位置可以任何位置（两只兔子也可以在同一块石头上）。例如有11个数，1 2 3 4 3 2 1 8 9 9 8，从第七个数断开，左边是一个长度为7的回文串，右边是一个长度为4的回文串，假设起点从4开始，一只顺时针、另一只逆时针，可以发现走的最多步数是11，即断开的两个回文串之和。不用考虑起点问题，因为两边的中点都可以作为起点。

状态方程：dp(i,j)=max(dp(i+1,j),dp(i,j-1));表示从i到j的最长非连续回文子序列。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+10;
    int a[maxn];
    int dp[maxn][maxn];
    int main(){
    	int n;
    	while(scanf("%d",&n)==1 && n){
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    			dp[i][i]=1;
    		}
    		
    		for(int len=2;len<=n;len++) //长度 
    		  for(int i=1;i<=n-len+1;i++){ //起始位置 
    		  	int j=i+len-1;   //终点位置 
    		  	dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
    		  	if(a[i]==a[j])
    		  	dp[i][j]=dp[i+1][j-1]+2;
    		  }
    		  
    		  int ans=0;
    		  for(int i=1;i<=n;i++)
    		  ans=max(ans,dp[1][i]+dp[i+1][n]);     //两段序列之和
    		  
    		  printf("%d\n",ans);
    	}
    	return 0;
    }

方法二：将序列长度加倍，找到长度为n的最长回文序列，但还需要考虑起点问题， 因为对于一个最长回文子序列可以选择一个不属于回文的石头作为起点，这样就从dp(i,i+n-1)和dp(i,i+n-2)+1中选择一个大的。

AC代码;

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+2;
    int a[maxn*2];
    int dp[maxn*2][maxn*2];
    int main(){
    	int n;
    	while(scanf("%d",&n)==1 && n){
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    			a[i+n]=a[i]; 
    			dp[i][i]=dp[i+n][i+n]=1;
    		}
    		
    		for(int len=2;len<=n*2;len++) //长度 
    		  for(int i=1;i<=2*n-len+1;i++){ //起始位置 
    		  	int j=i+len-1;   //终点位置 
    		  	dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
    		  	if(a[i]==a[j])
    		  	dp[i][j]=dp[i+1][j-1]+2;
    		  }
    		  
    		  int ans=0;
    		  for(int i=1;i<=n;i++)
    		  ans=max(ans,dp[i][i+n-1]);
    		  
    		  for(int i=1;i<=n;i++)
    		  ans=max(ans,dp[i][i+n-2]+1);
    		  printf("%d\n",ans);
    	}
    	return 0;
    }