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

· · 题解

题目大意

给出方块种类（<=400），求用现有的的方块在 使用数目不超过方块个数 ci ，方块所处高度不超过其最大限制高度 ai 时可以达到的最大高度

分析

“种类”、“个数”、“最大高度”等字眼再加上<=400的数据范围，相信大家很快就能够看出来这是一道DP，将“方块”作为“物品”，“高度”作为“体积”，显而易见——多重背包。

  1. 定义状态：注意到题目中“高度”一量既是所求答案又是运算的判断条件（即同时作为多重背包的“重量”和“价值”），所以我们可以考虑将f(i)定义为高度 i 是否可行，得出状态转移方程f(i)=f(i-h_{i})，特殊的：f(0)=1。

  2. 考虑边界：本题中边界有两个：ci和ai。在DP的循环条件中我们可以将ai作为循环终止的条件进行判断，现在考虑对方块使用个数ci的判断： 对于循环中的每种方块 i 达到的高度 j ，我们可以设定一个计数数组来记录这个状态下使用的方块 i 的个数，到达高度 j 时的使用个数就等于cnt(i,j-h_{i})+1。

  3. 特殊情况：在循环的途中我们发现，如果在前面的循环中计算了 ai 较大的方块，后面 ai 较小的方块将不会被计算，所以我们可以在DP前使用一个贪心策略：将方块按照 ai 从小到大排序。

有了上面的分析过程，相信代码也很快可以完成辣~

代码

#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~