POJ2392：Space Elevator

Space Elevator

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9244		Accepted: 4388

Description

The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

Input

* Line 1: A single integer, K

* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.

Output

* Line 1: A single integer H, the maximum height of a tower that can be built

Sample Input

Sample Output

题意是要搭梯子，要求的是梯子的最高能达到多少。限制条件一个是每个梯子有自身的限制高度，另外一个是梯子数量。

和POJ1014很像的思路，判断多高是判断每一个可能的高度其DP[]值是否为true，如果为true，记录其最大值即可。

我那种代码最后的内存会很大，没必要在sum上申请二维数组，一维的就足够了，每一次清零就好。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[40002];
int sum[40002][410];//数组一开始开小了
struct Node{
	int h;
	int cant;
	int num;
}node[500];

bool cmp(Node no1,Node no2)
{
	return no1.cant < no2.cant;
}


int main()
{
	int count;
	int i;

	cin>>count;
	for(i=1;i<=count;i++)
	{
		cin>>node[i].h>>node[i].cant>>node[i].num;
	}
	sort(node+1,node+1+count,cmp);

	memset(sum,0,sizeof(sum));
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	int j,ans=0;
	for(i=1;i<=count;i++)
	{
		for(j=node[i].h;j<=node[i].cant;j++)
		{
			if(!dp[j]&&dp[j-node[i].h]&&sum[j-node[i].h][i]<node[i].num)
			{
				sum[j][i] = sum[j-node[i].h][i]+1;
				dp[j]=1;
				if(j>ans)
					ans=j;
			}
		}
	}
	cout<<ans<<endl;

	return 0;
}