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

zju2057The Twin Towers,我的也是O(n^2)的时间复杂度,不知怎么超时了。麻烦看看

Posted by Aqyz at 2007-11-06 12:55:28
#include <cstdio>
#include <string>

int dp[101][2001], Towers;
int height[101];

int cmp(const void *a, const void *b)
{
	return (int *)a - (int *)b;
}
void input()
{
	int i;
	for(i=1; i<=Towers; i++)
	{
		scanf("%d", &height[i]);
	}
}

void my_dp();

int main()
{
	while(scanf("%d", &Towers), Towers != -1)
	{
		input();
		my_dp();
		if(dp[Towers][0] == 0)
			printf("Sorry\n");
		else
			printf("%d\n", dp[Towers][0]);
	}
	return 0;
}

inline int max3(int a, int b, int c)
{
	if(a > b)
	{
		if(a > c)
			return a;
		else
			return c;
	}
	else
	{
		if(b > c)
			return b;
		else
			return c;
	}
}

int value(int i, int j);
int add_low(int i, int j);

inline void my_dp()
{
	int i, j, sum = 0;
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for(i=1; i<Towers; i++)
	{
		sum += height[i];
		for(j=0; j<=sum && j<=1001; j++)
		{
			dp[i][j] = max3(value(i-1, j), value(i-1, j-height[i]), add_low(i-1, j+height[i]) );
			//					不加			上一个高处加				上一个矮处加
			//printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
		}
	}
	dp[Towers][0] = max3(value(Towers-1, 0),
		value(Towers-1, -height[Towers]), add_low(Towers-1, height[Towers]) );
}

inline int value(int i, int j)
{
	if(j < 0)							//上一个高处不满足 加到矮处
		if(dp[i][ -j ] != -1)
			return -j + dp[i][ -j ];	//高处的高度 相对高度+矮处的高度
		else
			return -1;
	else
		return dp[i][j];
}

inline int add_low(int i, int j)
{
	if(dp[i][j] != -1 )
		return dp[i][j] + height[i+1];	//矮处的高度 相对高度+矮处的高度
	return -1;
}
//4 10 11 1 3
//4 1 10 2 11
//4 1 9 10 2
//4 1 3 9 11
//4 11 9 3 1
//4 11 10 2 1
//上面很差的程序是我的,
//下面是网上抄的
#include<stdio.h>
#include<string.h>
int main()
{
	int n,i,sum,j,h;
	int a[2005],b[2005];
	while(scanf("%d",&n)&&n!=-1)
	{
		memset(a,-9999999,sizeof(a));
		a[0]=0;
		for(i=sum=0;i<n;i++)
		{
			memcpy(b,a,sizeof(a));
			scanf("%d",&h);
			sum+=h;
			for(j=0;j<=sum-h;j++)
				if(a[j+h]<b[j])
					a[j+h]=b[j];
			for(j=h+1;j<=sum;j++)
				if(a[j-h]<b[j]+h)
					a[j-h]=b[j]+h;
			for(j=0;j<=h;j++)
				if(a[h-j]<b[j]+j)
					a[h-j]=b[j]+j;
		}
		if(a[0]>0)printf("%d\n",a[0]);
		else printf("Sorry\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