题目地址:http://poj.org/problem?id=2392
题目大意:有一头奶牛要上太空,他有很多种石头,每种石头的高度是hi,但是不能放到ai之上的高度,并且这种石头有ci个
将这些石头叠加起来,问能够达到的最高高度。
解题思路:先将石头可以放置的最大高度按从小到大的顺序进行排序,
因为只有先放置最大高度最低的才能得到最优解,也就是说让一种石头尽可能高的放。
最大值必须初始化为0,因为存在高度为0的情况。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[400005]; struct node { int h,a,c; bool operator<(node &b) { return a < b.a; } }Arr[420]; int max(int a,int b) { return a > b ? a : b; } void zero_one_pack(int cost,int value,int v) {//0 1背包 for(int j = v; j >= cost ; j--) dp[j] = max(dp[j],dp[j-cost]+value); } void com_pack(int cost,int value,int v) {//完全背包 for(int j = cost ; j <= v; j++) dp[j] = max(dp[j],dp[j-cost]+value); } int main() { int k,i,n; while(scanf("%d",&n)!= EOF) { int a = 0,c = 0,h = 0; for(i = 0; i < n; i++) { scanf("%d%d%d",&Arr[i].h,&Arr[i].a,&Arr[i].c); } sort(Arr,Arr+n);//按最高限度从小到大排序 memset(dp,0,sizeof(dp)); int M = 0; for(i = 0; i < n; i++) {//printf("%d %d %d\n",Arr[i].h,Arr[i].a,Arr[i].c); if(Arr[i].c*Arr[i].h >= Arr[i].a)//完全背包 { com_pack(Arr[i].h,Arr[i].h,Arr[i].a); } else {//0 1背包,按二进制方式放物品 k = 1; while(k < Arr[i].c) { zero_one_pack(k*Arr[i].h,k*Arr[i].h,Arr[i].a); Arr[i].c -= k; k *= 2; } zero_one_pack(Arr[i].h*Arr[i].c,Arr[i].h*Arr[i].c,Arr[i].a); } /* if(dp[Arr[i].a] > M) M = dp[Arr[i].a]; */ } //不知道为什么要扫描数组,求解? for(i = 0; i <= Arr[n-1].a; i++) if(dp[i] > M)M=dp[i]; printf("%d\n",M); } return 0; }