n为奇数时为0；
偶数时：
把环打开，1~n，我们要做的，是连不交叉的线，环时不交叉的线，把数字排成一行时也是不交叉的，做dp， dp[i][j],为i到j连完不交叉的线后的最大的答案数(注意保持j-i+1是偶数！！！）。。。。
dp[i][j]=max(dp[i+1][j-1],dp[i][k]+dp[k+1][j])）；大致就是这样的dp，O(n*n)  dp



#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=1000;
int dp[N][N];
int a[N],n;
int dfs(int s,int t)
{
    int &d=dp[s][t];
    if(~d) return d;
    if(s==t-1)
    {
        return d=(a[s]==a[t]);
    }
    d=(a[s]==a[t])+dfs(s+1,t-1);
    for(int i=s+1;i<t;i+=2) d=max(d,dfs(s,i)+dfs(i+1,t));
    return d;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int w;cin>>w;
    while(w--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",a+i);
        if(n&1)
        {
            puts("0");
            continue;
        }
        memset(dp,-1,sizeof(dp));
        printf("%d\n",dfs(0,n-1));
    }
//    cout << "Hello world!" << endl;
    return 0;
}

• 你这个算法复杂度是n^3的，这儿卡常数啊，我环扩大一倍，再去做这个DP，TLE了。直接用循环算法是要5000MS+ (1067) yygy 2013-06-05 16:17:48
• Re:这个想法不错啊，非递归dp，1500+ms (1067) zhanggt1994 2014-03-20 19:58:21