题解 P6771 【[USACO05MAR]Space Elevator 太空电梯】

### 题目大意 给出方块种类（<=400），求用现有的的方块在 **使用数目不超过方块个数 ci ，方块所处高度不超过其最大限制高度 ai** 时可以达到的最大高度 ### 分析 “种类”、“个数”、“最大高度”等字眼再加上<=400的数据范围，相信大家很快就能够看出来这是一道DP，将“方块”作为“物品”，“高度”作为“体积”，显而易见——**多重背包**。 1. 定义状态：注意到题目中“高度”一量既是所求答案又是运算的判断条件（即同时作为多重背包的“重量”和“价值”），所以我们可以考虑**将$f(i)$定义为高度 i 是否可行**，得出状态转移方程$f(i)=f(i-h_{i})$，特殊的：$f(0)=1$。 1. 考虑边界：本题中边界有两个：ci和ai。在DP的循环条件中我们可以将ai作为循环终止的条件进行判断，现在考虑对方块使用个数ci的判断： 对于循环中的每种方块 i 达到的高度 j ，我们可以设定一个计数数组来记录这个状态下使用的方块 i 的个数，**到达高度 j 时的使用个数就等于$cnt(i,j-h_{i})+1$**。 1. 特殊情况：在循环的途中我们发现，如果在前面的循环中计算了 ai 较大的方块，后面 ai 较小的方块将不会被计算，所以我们可以在DP前使用一个**贪心策略**：将方块按照 ai 从小到大排序。 有了上面的分析过程，相信代码也很快可以完成辣~ ### 代码 ```cpp #include<cstdio> #include<algorithm> using namespace std; const int M=200000; int n,ans=0; struct node{ int h,c,a; }p[405]; int cnt[405][M]; bool f[M]; bool cmp(node x,node y) {return x.a<y.a;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&p[i].h,&p[i].a,&p[i].c); sort(p+1,p+n+1,cmp);//将方块按照ai排序以避免出错 f[0]=1; for(int i=1;i<=n;i++) for(int j=p[i].h;j<=p[i].a;j++) if(f[j-p[i].h]&&!f[j]&&cnt[i][j-p[i].h]<p[i].c){//在这里必需要有“!f[j]”的判断，以防cnt被重复计算 cnt[i][j]=cnt[i][j-p[i].h]+1; f[j]=1; ans=max(ans,j);//ans记录答案（可行的最大高度） } printf("%d",ans); return 0; } ``` 完结撒fa~