hdoj 4745 Two Rabbits (最长不连续回文子序列 环形DP)

http://acm.hdu.edu.cn/showproblem.php?pid=4745
参考博客：http://blog.csdn.net/cc_again/article/details/11852367
环形区间DP求最长不连续回文子序列；
以前做环形都是倍增，这次学到了新的思路，因为是回文，正着反着都一样，然后环形就可以分成$[1,i]$和$[i+1,n]$两部分，那么A从$i+1$走到$n$，再走到$1$，再从$1$走到$i$，同样的B可以从$i$走到$1$，再走到$n$，再从$n$走到$i+1$，A和B就都把把整个环走完了。
最长不连续回文子序列的状态转移方程就是
$f[i][j]=max(f[i+1][j],f[i][j-1],if(a[i]==a[j]) f[i+1][j-1]+2)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int f[1010][1010],a[1010],n;
int main()
{while(scanf("%d",&n)&&n!=0){int ans=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){scanf("%d",&a[i]);//a[i+n]=a[i]; f[i][i]=1;}for(int i=2;i<=n*2;i++)//因为每次需要从较短的长度转移到较长的长度，所以要用这种技巧遍历，注意i=2开始 {for(int j=1;j+i-1<=n*2;j++){int k=j+i-1;f[j][k]=max(f[j][k],max(f[j+1][k],f[j][k-1]));if(a[j]==a[k])f[j][k]=max(f[j][k],f[j+1][k-1]+2);}}for(int i=1;i<=n;i++)ans=max(ans,f[1][i]+f[i+1][n]);//环形，所以a[1]和a[n]相连，所以取f[1][i]+f[i+1][n]的最大值即为答案；若为链形，f[1][n]即为答案 printf("%d\n",ans);}return 0;
}