题解 P6771 【[USACO05MAR]Space Elevator 太空电梯】
lzqy_
·
·
题解
一道挺好的动态规划练手题。
思路
我们使 f[i] 表示是否能堆高度为
$$\begin{cases}\quad f[0]=1\\\quad f[i]=max\{f[i-h_j]\}(1\le j\le n)\end{cases}$$
第一层循环 $1$ ~ $n$，第二层循环 $h_j$ ~ $a_j$（即枚上述转移方程中的 $i$） 即可。
---
这就大功告成了？不，我们还有一些条件没有考虑到。
比如说，现在有一块高度为 $1$ 的石头，不能超过高度 $100$；还有一块高度为 $10$ 的石头，不能超过高度 $10$。
按照我们的动态转移方程，先看第一块石头，得 $f[1]=1$；然后就无法再堆任何石头了。
所以，我们需要先把石头按照 $a_i$ 排个序，把 $a_i$ 较小的石头放下面， $a_i$ 较大的石头放上面。
-------
但是我们还是少考虑了一个情况，即 $c_i$ 的限制。
所以我们还要再用一个数组 $cnt[i][j]$ 表示高度为 $j$ 的魔法塔需要多少块 $j$ 号魔法石。
## 实现
在 cnt 数组的实现中，其实还是有一个贪心的小细节在其中的，结合代码来理解吧（有详细注释）：
```cpp
#include <bits/stdc++.h>
using namespace std;
int k[10001],ans;
int cnt[401][10001];
struct p
{
int h,a,c;
} b[401];
bool cmp(p a,p b)
{
return a.a<b.a;
}
int n;
int main()
{
k[0]=1;
cin>>n;
for(int i=1; i<=n; i++)
cin>>b[i].h>>b[i].a>>b[i].c;//读入
sort(b+1,b+1+n,cmp);//排序
for(int i=1; i<=n; i++)
{
for(int j=b[i].h; j<=b[i].a; j++)
{
if(k[j]==1)
continue;
if(k[j-b[i].h]==1&&cnt[i][j-b[i].h]<b[i].c)
{
k[j]=k[j-b[i].h];
cnt[i][j]=cnt[i][j-b[i].h]+1;
ans=max(j,ans);//
}
/*这两个if语句用到了一个贪心的思路
对于高度j，可能有多种的摆搭方式，
按照贪心的思路，我们应让第i块石头尽量少
第1~i-1块石头尽量多
（因为1~i-1的状态是已经确定的了，
所以为了目前能垒的更高，所以要尽量少用当前的石头）
因此，如果k[j]已经有值了，说明能用更少的第i块石头
垒出高度为j的太空电梯，所以不用变动cnt的值，直接continue;*/
}
}
cout<<ans<<endl;
return 0;
}
```
### 祝大家AC愉快！