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;

}

巴特西

POJ2392：Space Elevator

最新文章

热门文章