首页 > ACM题库 > HDU-杭电 > HDU 4314-Save the dwarfs-动态规划-[解题报告]HOJ
2015
05-23

HDU 4314-Save the dwarfs-动态规划-[解题报告]HOJ

Save the dwarfs

问题描述 :

Several dwarfs are trapped in a deep well. They are not tall enough to climb out of the well, so they want to make a human-pyramid, that is, one dwarf stands on another’s shoulder, until the dwarf on the top can reach the top of the well when he raise his arms up. More precisely speaking, we know the i-th dwarf’s height from feet to shoulder is Ai, and his arm length Bi. And we know the height of the well is H. If we can build a dwarf-tower consists of dwarf 1, dwarf 2, …, dwarf k from bottom to top, such that A1 + A2 + … + Ak-1 + Ak + Bk >= H, then dwarf k can escape from the well. Obviously, the escaped dwarf can’t be used to build tower again.

We want the escaped dwarfs as many as possible. Please write a program to help the dwarfs.

输入:

The first line of each test case contains N, (1 <= N <= 2000) the number of trapped dwarfs. Each of the following N lines contains two integers Ai and Bi. The last line is H, the height of the well. All the integers are less than 100,000.

输出:

The first line of each test case contains N, (1 <= N <= 2000) the number of trapped dwarfs. Each of the following N lines contains two integers Ai and Bi. The last line is H, the height of the well. All the integers are less than 100,000.

样例输入:

2
20 10
5 5
30
2
20 10
5 5
35

样例输出:

2
1
Hint
For the first case, the tall dwarf can help the other dwarf escape at first. For the second case, only the tall dwarf can escape.

/*
分析:
    dp。
    “一个重要的观察是,如果某些矮人可以逃脱,那么我们总可以把他们的
逃脱顺序按照Ai+Bi递增排序(即Ai+Bi最小的先逃脱),得到的结果不会更
坏。”,这个发现我是没有发现囧~,不过证明了一下:
    有n个人,设每个人的高度为hi、手长li、总长ti,现在这n个人中有a、b
以及其他人,a、b是ti最小的俩,且tb>=ta,设其他人的总身高为base,那么:
        如果a站在base上面可以出去,那么b站在base上面也可以出去;
        而如果b站在b上面可以出去,那么a站在base上面不一定可以出去;
        所以让a站在base+b上面,试试能不能让a先出去,总归不是一个更坏
    的决策;
        把这个关系推到全局,那么没有比“尽量让ti最小的先出去”更好的决策。

    dp[i][j]表示最后i个人能逃出j个时,需要之前井中剩下的人的最小A高
度之和。则转移方程:
dp[i][j] = min(dp[i-1][j] – s[i-1].a, max(dp[i-1][j-1], H – sumA[i-1] – s[i-1].b )),
满足dp[i][j]<=0的最大的j既为所求。

                                                        2013-04-22
*/

#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int N=2012;

int n,limit;
int sum[2012],dp[2][2012];
struct node{
	int h,l;
}E[N];

int min(int a,int b){
	return a>b?b:a;
}
int max(int a,int b){
	return a>b?a:b;
}
int cmp(node n1,node n2){
	return n1.h+n1.l>n2.h+n2.l;
}
int solve()
{
	int i,l;
	int pre,now,t=1<<30;
	int ans=0;
	dp[0][0]=0;
	for(l=1;l<=n;l++)	dp[0][l]=t;
	for(i=1;i<=n;i++)
	{
		now=i%2;
		pre=1-now;
		for(l=0;l<=i;l++)	dp[now][l]=0;
		for(;l<=n;l++)		dp[now][l]=t;
		for(l=1;l<=i;l++)
		{
			dp[now][l]=min(dp[pre][l]-E[i].h,max(dp[pre][l-1],limit-sum[i]-E[i].l));
			if(dp[now][l]<=0 && ans<l)	ans=l;
		}
	}
	return ans;
}
int main()
{
	int i;
	while(scanf("%d",&n)!=-1)
	{
		for(i=1;i<=n;i++)	scanf("%d%d",&E[i].h,&E[i].l);
		scanf("%d",&limit);
		E[0].h=E[0].l=0;
		sum[0]=0;
		sort(E+1,E+n+1,cmp);
		for(i=1;i<=n;i++)	sum[i]=sum[i-1]+E[i].h;
		printf("%d\n",solve());
	}
	return 0;
}

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

参考:http://blog.csdn.net/ice_crazy/article/details/8836253