TYVJ P1086 Elevator Label:dp

背景

广东汕头聿怀初中 Train#2 Problem4

描述

现有N种箱子,每种箱子高度H_i,数量C_i。现选取若干箱子堆成一列,且第i种箱子不能放在高度超过A_i的地方。试求最大叠放高度。

输入格式

第一行,一个整数,表示箱子种类N。
接下来N行,每行三个整数,表示H_i,A_i,C_i。

输出格式

一个整数,表示最大高度。

测试样例1

输入


7 40 3 
5 23 8 
2 52 6

输出

48

备注

N <= 400 , H_i <= 100 , C_i <= 10 , A_i <= 40000
Vivian Snow

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct cc{
int h,a,c;//h箱子高度 a最大高度 c数量
}node[];
bool cmp(cc a,cc b){
return a.a<b.a;
}
int N,ans,f[]; void print(){//测试用
puts("");
for(int i=;i<=;i++) printf("h=%-2d %-2d\n",i,f[i]);
puts("");
} int main(){//顶端不可以超过a
// freopen("01.txt","r",stdin);
memset(f,,sizeof(f));
f[]=;
scanf("%d",&N);
for(int i=;i<=N;i++)scanf("%d%d%d",&node[i].h,&node[i].a,&node[i].c);
sort(node+,node+N+,cmp);
for(int i=;i<=N;i++){
for(int j=node[i].a;j>=node[i].h;j--){//逆序,以保证无后效性
if(f[j-node[i].h]>){//如果这个高度可以放
for(int k=;k<=node[i].c;k++){//把能叠的都叠上去
if(j-node[i].h +k*node[i].h<=node[i].a) {//避免越界
f[j-node[i].h +k*node[i].h]++;
ans=max(ans,j-node[i].h+k*node[i].h);//更新高度
}
}
}
} // print(); }
printf("%d\n",ans);
return ;
}

详见注释啦,讲的很清楚了,注意逆序,条件略多,勿喷。

上一篇:TYVJ P1034 尼克的任务 Label:倒推dp


下一篇:Python练习题 002:奖金计算