首页 > ACM题库 > HDU-杭电 > HDU 4001-To Miss Our Children Time-动态规划-[解题报告]HOJ
2015
04-14

HDU 4001-To Miss Our Children Time-动态规划-[解题报告]HOJ

To Miss Our Children Time

问题描述 :

Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game will brings us lots of happy time! LLL is a nostalgic boy, now he grows up. In the dead of night, he often misses something, including a simple game which brings him much happy when he was child. Here are the game rules: There lies many blocks on the ground, little LLL wants build "Skyscraper" using these blocks. There are three kinds of blocks signed by an integer d. We describe each block’s shape is Cuboid using four integers ai, bi, ci, di. ai, bi are two edges of the block one of them is length the other is width. ci is
thickness of the block. We know that the ci must be vertical with earth ground. di describe the kind of the block. When di = 0 the block’s length and width must be more or equal to the block’s length and width which lies under the block. When di = 1 the block’s length and width must be more or equal to the block’s length which lies under the block and width and the block’s area must be more than the block’s area which lies under the block. When di = 2 the block length and width must be more than the block’s length and width which lies under the block. Here are some blocks. Can you know what’s the highest "Skyscraper" can be build using these blocks?

输入:

The input has many test cases.
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks.
From the second to the n+1′th lines , each line describing the i�\1′th block’s a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2).
The input end with n = 0.

输出:

The input has many test cases.
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks.
From the second to the n+1′th lines , each line describing the i�\1′th block’s a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2).
The input end with n = 0.

样例输入:

3
10 10 12 0
10 10 12 1
10 10 11 2
2
10 10 11 1
10 10 11 1
0

样例输出:

24
11

题意:给你些积木,分三类,0:只能放在小于等于它的长和宽的积木上,1:只能放在长和宽小于等于它且面积小于他的木块上,2:只能放在长和宽偶小于它的木块上。求积木的最高高度。

显然dp,排一下序,dp一下就出结果了,可惜我wa了几次,在求面积的时候溢出了,太不小心了,记过。

状态和转移都很好想,就不说了,很晚了,睡觉了。。。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4597349 2011-09-14 01:42:20 Accepted 4001 46MS 324K 1227 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct block
{
	int x,y,z,d;
}b[1005];
long long dp[1005];
int n;
bool cmp(block a,block b)
{
	if(a.x!=b.x)return a.x<b.x;
	if(a.y!=b.y)return a.y<b.y;
	return a.d>b.d;
}
void DP()
{
	long long ans=b[0].z;
	for(int i=0;i<n;i++)
	{
		dp[i]=b[i].z;
		ans=max(ans,dp[i]);
	}
	for(int i=1;i<n;i++)
	{
		if(b[i].d==0)
		{
			for(int j=0;j<i;j++)
			{
				if(b[j].x<=b[i].x&&b[j].y<=b[i].y)
					dp[i]=max(dp[i],dp[j]+b[i].z);
			}
		}
		if(b[i].d==1)
		{
			for(int j=0;j<i;j++)
			{
				if(b[j].x<=b[i].x&&b[i].y>=b[j].y&&(b[i].y*b[j].y||b[i].x>b[j].x))
					dp[i]=max(dp[i],dp[j]+b[i].z);
			}
		}
		if(b[i].d==2)
		{
			for(int j=0;j<i;j++)
			{
				if(b[i].x>b[j].x&&b[i].y>b[j].y)
				{
					dp[i]=max(dp[i],dp[j]+b[i].z);
				}
			}
		}
	    ans=max(ans,dp[i]);  
	}
	cout<<ans<<'\n';
}

int main()
{
	while(1)
	{
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++)
		{
			scanf("%d%d%d%d",&b[i].x,&b[i].y,&b[i].z,&b[i].d);
			if(b[i].x<b[i].y)
				swap(b[i].x,b[i].y);
		}
		sort(b,b+n,cmp);
		DP();
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xymscau/article/details/6773117


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。