[HDU4745] Two Rabbits (区间DP)

题目链接

Solution

区间DP。
显然是统计最长的回文序列.
状态定义:
令 (f[i][j]) 表示 (i) 到 (j) 的最长回文序列长度.
状态转移:

1. (s[i] eq s[j])
   那么此时 (f[i][j]) 即为(f[i][j-1]),(f[i+1][j])种较大的那个.
   但由于 (i+1->j-1)的我们明显重复统计了,所以方程即为:

[f[i][j]=max(f[i+1][j],f[i][j-1]) ]

2. $s[i]=s[j]$ 此时考虑,对于 $i+1$ 到 $j-1$ 中的回文序列,我们都可以把 $s[i]$和$s[j]$ 加在两边.长度多2. 所以此时方程即为: $$f[i][j]=f[i+1][j-1]+2$$

最后还要考虑是否从同一起点出发.
若从同一起点出发,那么答案即为 (f[i][i+n-2]+1).
否则就为 (f[i][i+n-1])

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1008;
int f[maxn][maxn];
int n,t,s[maxn];
int ans;

int main()
{
	while(1)
	{
		scanf("%d",&n);
		if(n==0)return 0;
		ans=1;
		memset(f,0,sizeof(f));
		for(int i=0;i<n;i++)
		{
			scanf("%d",&s[i]);
			s[i+n]=s[i];
		}
		for(int i=0;i<2*n;i++)
		{
			f[i][i]=1;
			if(i>0){
			if(s[i]==s[i-1])
			f[i-1][i]=2;
			else f[i-1][i]=1;	
			}
		}
		for(int len=3;len<=n;len++)
		for(int l=0;l<=2*n-len;l++)
		{
			int r=l+len-1;
			if(s[l]==s[r])
			f[l][r]=(f[l+1][r-1]+2);
			else 
			f[l][r]=max(f[l][r-1],f[l+1][r]);
			ans=max(ans,f[l][r]);
		}
		
  		for (int i=0;i<=n;i++)
  		{
      		ans=max(ans,f[i][i+n-1]);
      		ans=max(ans,f[i][i+n-2]+1);
  		}	
		printf("%d
",ans);
	}		
}