2013 ACM/ICPC Asia Regional Hangzhou Online
1008 Two Rabbits
这个题的大体意思是给n个点构成一个环，每个点有一个权值，两个兔子各自选择一个任选一个点作为起点开始跳，两人同时跳，一个逆时针，一个顺时针，跳跃的距离不限制，有三个条件： 1、以前跳过了就不要再跳到这个点 2、不能跨过以前跳过的点 比如说以前走过2了，那么这次在1号点的话，就不能到2,3,4…… 如果是顺时针的话 3、每一时刻两人所在的点权值都必须一样
刚开始讨论的是破环成链，长度扩展成2倍，然后正逆两条，然后用最长公共公共子串，dp[i][j]预处理，然后再枚举开头，减去相应的前缀，但是后来发现不行啊，没法减去啊，因为dp过程中相邻的会造成影响传递，减去dp[i-n][j-n]或者dp[i-n+1][j-n]之类的并不一定能消掉啊，因为影响是交叉影响的，dp[i][i-n-m]可能也会对相应的n段内造成影响，无法相减！！
后来看了赛后的解题报告才知道，不要破环，就不会造成影响了，不破环然后看成回文串，然后在会问的过程中推导发现一些规律， 比如说i-j这一段的回文可能扩展成i-1 --- j+1的回文，如果条件合适的话！ 那么我们找出dp[i][j] 表示i-j段的最大回文子串， 然后0 a b a 0 1可以看成 0-0这段加上单独的1那一段， 反正至少有一个起点在两端！！
代码来自赛后解题报告，我加了注释而已 原网址的话自己到ACM信息站去找吧 http://acmicpc.info/archives/1563
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[1009][1009];///记录从i到j位置的最长回文子串的长度
int n,arr[1009];
int DP()
{///想成一只兔子在走就好了,只不过走的是回文串，妙啊啊啊啊！
/// 注意如果两个人的起点是 2,5的话，那么一定能将起点改为1,6； 如果1,6曾在且形同的情况下(所以一定能扩展成一个起点一定在两头)，
///注意0 a b a c d c 0的情况下是6
///0 a b a 0 d 可以看做两个人从a开头，也可以看做从0开头……
/// 0 1 2 1 3 4 3 5 6 5 0 注意这种形式，中间的三对没法全部利用
int ans=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<=n;i++) dp[i][i]=1;
for(int i=n-1;i>0;i--)
{
for(int j=i+1;j<=n;j++)
{
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
if(arr[i]==arr[j]) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);//头和尾相同，则长度可加2
}
}
for(int i=1;i<=n;i++) ans=max(ans,dp[1][i]+dp[i+1][n]); //枚举起点
return ans;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("testin.txt","r",stdin);
// //freopen("testout.txt","w",stdout);
//#endif
while(scanf("%d",&n)&&n)
{
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
printf("%d\n",DP());
}
return 0;
}