#include <iostream>

using namespace std;

const int N = 1000 + 10;
int dp[N][N];
bool flag[N][N];
int a[N * 2];
int cnt[100 + 10];
int n;

int run(int s, int L)
{
	if (flag[s][L]) return dp[s][L];
	flag[s][L] = true;
	if (L == 2)
	{
		if (a[s] == a[s + 1]) dp[s][L] = 1;
		else dp[s][L] = 0;
		return dp[s][L];
	}
	dp[s][L] = INT_MIN;
	if (a[s] == a[s + 1]) dp[s][L] = max(dp[s][L], 1 + run((s + 2) % n, L - 2));
	else dp[s][L] = max(dp[s][L], run((s + 2) % n, L - 2));
	if (a[s] == a[s + L - 1]) dp[s][L] = max(dp[s][L], 1 + run((s + 1) % n, L - 2));
	else dp[s][L] = max(dp[s][L], run((s + 1) % n, L - 2));
	int t;
	for (t = s + 3; t < s + L - 1; t += 2)
	{
		if (a[s] == a[t]) dp[s][L] = max(dp[s][L], 1 + run((s + 1) % n, t - s - 1) + run((t + 1) % n, s + L - t - 1));
		else dp[s][L] = max(dp[s][L], run((s + 1) % n, t - s - 1) + run((t + 1) % n, s + L - t - 1));
	}
	return dp[s][L];
}

int main()
{
	int casenum, i, j;
	scanf("%d", &casenum);
	while (casenum--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; ++i) scanf("%d", a + i);
		memcpy(a + n, a, sizeof(int) * n);
		memset(flag, 0, sizeof(flag));
		printf("%d\n", run(0, n));
	}
	return 0;		
}

• 你的愣是没看懂||=.=。。你看看我的吧。 (368) ACM06060 2007-10-12 13:06:31
  • 感觉你超时就是因为计算步数太多了吧。。每次都算那么多种情况这题卡的又严 (406) ACM06060 2007-10-12 13:08:04
• 不用考虑wrap-around的情况 (1310) frkstyc 2007-10-12 13:08:24
• 还是不行 >.< (696) cuiaoxiang 2007-10-12 13:09:19
  • 还是写成循环吧…… (776) frkstyc 2007-10-12 13:14:57
  • 告诉你个大招~改成.h不用using namespace (0) ACM06060 2007-10-12 13:20:41
    • 就可以过了吧 (0) ACM06060 2007-10-12 13:21:01
      • 这个题就那么一丁点儿数据……这个没用 (0) frkstyc 2007-10-12 13:22:43
        • 可是我就把他代码改了就过了嘿。。。 (0) ACM06060 2007-10-12 13:24:19
          • 2780706 ACM06060 3056 Accepted 4108K 4640MS C++ 596B (0) ACM06060 2007-10-12 13:24:53
            • 刚才在rejudge.... (0) frkstyc 2007-10-12 13:27:07
              • 。。。。。。。 (0) ACM06060 2007-10-12 13:29:53