算法很简单,问题是,怎么证明,答案是回文序列.
设a,b走的序列按顺时针是:
a1 , a2 , a3 , ... , ak
b1 , b2 , b3 , ... , bk
考虑端点的2种情况:
1. a1 b1 ... bk ak
2. a1 b1 ... ak bk
对于第一种, 将b1,bk移动到a1,ak ,不会让答案变小, 于是这种情况下的答案为 [i,i+n-1]区间的回文序列长度
对于情况2, bk对应的下标如果小于a1，那么同样可以进行情况1的操作, 如果 bk的下标>a1那么
a,b都在两个不想交的区间移动,并且两个区间的总长小于n, 于是答案仍然为 [i,i+n-1]区间的回文序列长度;
如果bk == a1, 是a,b是从同一个点出发的情况, 答案 为 [i,i+n]区间的回文序列长度-1, 因为起点算了多次,要减1.
#include <map>
#include <queue>
#include <ctime>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long llong;
#define ls ((l+r)<<1)
#define rs (((l+r)<<1)+1)
#define mid ((l+r)>>1)
#define maxn 2010 int n,a[maxn],f[maxn][maxn]; int getvar(int l,int r)
{
if (l>r) return ;
if (l==r) return f[l][r] = ;
if (f[l][r] != -) return f[l][r];
int res = ;
if (a[l]==a[r]) res = getvar(l+,r-)+;
res = max(res,getvar(l+,r));
res = max(res,getvar(l,r-));
return f[l][r] = res;
} int main()
{
freopen("test.txt","r",stdin);
while (scanf("%d",&n))
{
if (!n) break;
for (int i= ; i<=n ; i++ ) scanf("%d",&a[i]);
for (int i= ; i<=n ; i++ ) a[i+n] = a[i];
int ans = ;
memset(f,-,sizeof(f));
for (int i= ; i<=n ; i++ )
{
int tmp = getvar(i,i+n-);
ans = max(ans,tmp);
tmp = getvar(i,i+n) - ;
ans = max(ans,tmp);
}
printf("%d\n",ans);
}
return ;
}