HDU 4314 Contest 2

可以知道，逃出的人中，最后一个应当是A+B最长的，这是很容易发现的。那么，最选逃出去的必定是A+B最短的。这符合最优。

于是，可以把各小矮人按A+B的和由大到小排序。定义DP[i][j]为i个人中逃出了j个人至少需要“之前”的留在井中的未逃出去的小矮人的高度和。注意这个值是可以为负数的，是负数，则证明需要之前有人留下，这些i个人足可以把j个人送出去。

那么，有DP[i][j]=min{dp[i-1][j]-a[i],max(dp[i-1][j-1],H-sumA[i]-b[i])}。

解释一下递推方程，当第i个人未逃出去时，则第i个人留下，即需要满足dp[i-1][j]的人的高度减去第i个的高度。显而易见。

当第i个人逃出去时，为什么需要max(dp[i-1][j-1],H-sumA[i]-b[i])。因为前i-1个人逃出去j-1个（i必定最先逃出）的A高度未必一定满足使第i个人逃出去的高度（最先逃出），而若H-sumA[i]-b[i]的高度能使第i个人逃出去，则必定满足后j-1个人逃出。因为第i个是最先逃出的。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int dp[2010];

struct dwarf{

	int a,b;

	int sum;

}dw[2010];

int sumA[2010];

bool cmp(dwarf a,dwarf b){

	if(a.sum>b.sum)

	 return true;

	 return false;

}

int main(){

	int n,H;

	while(scanf("%d",&n)!=EOF){

		for(int i=1;i<=n;i++){

			scanf("%d%d",&dw[i].a,&dw[i].b);

			dw[i].sum=dw[i].a+dw[i].b;

		}

		scanf("%d",&H);

		sort(dw+1,dw+1+n,cmp);

		sumA[0]=0;

		for(int i=1;i<=n;i++){

			dp[i]=(1<<30);

			sumA[i]=sumA[i-1]+dw[i].a;

		}

		for(int i=1;i<=n;i++){

			for(int j=i;j>=1;j--){

				dp[j]=min(dp[j]-dw[i].a,max(dp[j-1],H-dw[i].b-sumA[i]));

			}

		}

		int k=0;

		for(int i=1;i<=n;i++)

		if(dp[i]<=0)

		k=i;

		printf("%d\n",k);

	}

	return 0;

}

巴特西

HDU 4314 Contest 2

最新文章

热门文章