| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
zju2057The Twin Towers,我的也是O(n^2)的时间复杂度,不知怎么超时了。麻烦看看#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator