[Luogu] P4823 [TJOI2013]拯救小矮人

(Link)

Description

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的肩膀上，直到最顶端的小矮人伸直胳膊可以碰到陷阱口。

对于每一个小矮人，我们知道他从脚到肩膀的高度(A_i)，并且他的胳膊长度为(B_i)。陷阱深度为(H)。

如果我们利用矮人(1)，矮人(2)，矮人(3)，...，矮人(k)搭一个梯子，满足(A_1+A_2+A_3+....+A_k+B_k>=H),那么矮人(k)就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。

我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。

Solution

贪心(+DP)。

手动模拟一下就发现不能按(A_i)从小到大排序，肯定和(B_i)是有关的。

我们贪心选择逃生能力较弱的人先逃出去（即(A_i+B_i)较小），这样排序以后就不会出现后面的人先逃出去比前面的人先逃出去更优的情况。（因为如果前面的人能逃出去，把后面的人换到这个位置来一样能逃出去。但如果后面的人先逃出去，前面的人可能会因为没有人垫着而逃不出去了。）

做个背包就行了，设(dp[i])表示走(i)个人后可以取的最大高度，那么有$。dp[1sim{n}]=-INF,dp[0]=sum{A_i}。 $

转移方程为(dp[j]=max{dp[j-1]-A_i}(dp[j-1]+B_ige{H}))

Code

#include <bits/stdc++.h>

using namespace std;

int n, h, dp[2005];

struct node
{
	int a, b;
}p[2005];

int read()
{
	int x = 0, fl = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * fl;
}

int cmp(node x, node y)
{
	return x.a + x.b < y.a + y.b;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; i ++ )
	{
		p[i].a = read();
		p[i].b = read();
	}
	h = read();
	sort(p + 1, p + n + 1, cmp);
	memset(dp, -0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i = 1; i <= n; i ++ )
		dp[0] += p[i].a;
	for (int i = 1; i <= n; i ++ )
		for (int j = i; j >= 1; j -- )
			if (dp[j - 1] + p[i].b >= h)
				dp[j] = max(dp[j], dp[j - 1] - p[i].a);
	for (int i = n; i >= 0; i -- )
	{
		if (dp[i] >= 0)
		{
			printf("%d
", i);
			break;
		}
	}
	return 0;
}