洛谷 P4823 [TJOI2013]拯救小矮人（贪心）

【题目】

https://www.luogu.com.cn/problem/P4823

【审题】

设当前已搭人梯高度为h，当前小矮人为k。

逃出条件：h+a[k]+b[k]>=H

【思路】

首先，将小矮人以a+b递增的顺序排序。

然后进行背包。

设f[i][j]为前i个人中逃出j个时人梯的最大高度。

则第i个人可以走或不走。如果走，f[i]=f[i-1]-a[i]；如果不走，f[i]不变。

状态转移方程：dp[i] = max(dp[i], dp[i-1] - a[i].p);

【分析】

其实按照上述【审题】中所写，反倒限制了dp的思路

问：为什么要按a+b来排序？

　　答：如图，若人梯已定，只有1和2两个人未确定是否能逃出时，若按左边方案走，两个人都能走，按右边方案，只能走一个人。

【代码实现】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 struct peo
 5 {
 6     int p,q;
 7     bool operator<(const peo &a) const
 8     {
 9         return a.p+a.q>p+q;
10     }
11 }a[10005];
12 int dp[10005];
13 int h;
14 int main()
15 {
16     scanf("%d",&n);
17     for(int i=1;i<=n;i++)
18     {
19         scanf("%d %d",&a[i].p,&a[i].q);
20     }
21     sort(a+1,a+1+n);
22     scanf("%d",&h);
23     for(int i=1;i<=n;i++)
24     {
25         dp[i]=-1e9;
26         dp[0]+=a[i].p;
27     }
28     for(int i=1;i<=n;i++)
29     {
30         for(int j=i;j>=1;j--)
31         {
32             if(dp[j-1] + a[i].q >= h)
33             {
34                 dp[j]=max(dp[j],dp[j-1]-a[i].p);
35             }
36         }
37     }
38     for(int i = n; i >= 0; --i)
39         if(dp[i] >= 0) {
40             printf("%d\n", i);
41             return 0;
42         }
43     return 0;
44 }