Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我也是 >.< 谁能帮我看看吗?

Posted by cuiaoxiang at 2007-10-12 00:06:22 on Problem 3056
In Reply To:我也是 >.< 谁能帮我看看吗? Posted by:cuiaoxiang at 2007-10-12 00:04:43
#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;		
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator