Description

奶牛们想用K(1<=K<=400)中石块制造一个太空电梯去太空旅行，每种石块有自己的高度h_i(1<=h_i<=100)和数量c_i(1<=c_i<=10),为了避免宇宙射线的干扰，每种石块不能超过最高可以达到的高度a_i(1<=a_i<=40000)。
　　帮助奶牛用石块堆积一个最高的太空电梯。

Input

第1行：一个整数K
　　第2到K+1行：每行3个用空格隔开的整数h_i,a_i,c_i

Output

输出一个高度H，表示最大高度。

Sample Input

3
7 40 3
5 23 8
2 52 6

Sample Output

48

Data Constraint

Hint

【样例说明】
　　从上到下依次是6个3号石块、3个1号石块和3个2号石块，注意放4个2号石块在3个1号石块的下面是不行的，因为1号石块最高不能超过40，而现在最上面的1号石块高度达到41，所以不行。

.
.
.
.
.
分析
设f[i,j]为前i种石头，高度为j是否可行，显然是个判定性的dp

.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int k,a[500],h[500],c[500];
bool f[50000];void kp(int l,int r)
{if (l>r) return;int i=l,j=r,mid=a[(l+r)/2];do{while (a[i]<mid) i++;while (a[j]>mid) j--;if (i<=j){h[0]=h[i];h[i]=h[j];h[j]=h[0];a[0]=a[i];a[i]=a[j];a[j]=a[0];c[0]=c[i];c[i]=c[j];c[j]=c[0];i++;j--;}}while (i<j);kp(l,j);kp(i,r);
}int main()
{scanf("%d",&k);for (int i=1;i<=k;i++)scanf("%d%d%d",&h[i],&a[i],&c[i]);kp(1,k);memset(f,false,sizeof(f));f[0]=true;for (int i=1;i<=k;i++){for (int j=a[i];j>=0;j--){for (int k=1;k<=c[i];k++){if (j+k*h[i]>a[i]) break;if (f[j]) f[j+k*h[i]]=true;}}}for (int i=a[k];i>=0;i--)if (f[i]){cout<<i;break;}return 0;
}

转载于:https://www.cnblogs.com/YYC-0304/p/11094945.html

太空电梯-编程知识网与50位技术专家面对面20年技术见证，附赠技术全景图