做彩票网站收费标准,郑州企业网站seo,产品外观设计的重要性,网站建设一般一年多少费用题目地址#xff1a;http://poj.org/problem?id2392 题目大意#xff1a;有一头奶牛要上太空#xff0c;他有很多种石头#xff0c;每种石头的高度是hi#xff0c;但是不能放到ai之上的高度#xff0c;并且这种石头有ci个 将这些石头叠加起来#xff0c;问能够达到的最…题目地址http://poj.org/problem?id2392 题目大意有一头奶牛要上太空他有很多种石头每种石头的高度是hi但是不能放到ai之上的高度并且这种石头有ci个 将这些石头叠加起来问能够达到的最高高度。 解题思路先将石头可以放置的最大高度按从小到大的顺序进行排序 因为只有先放置最大高度最低的才能得到最优解也就是说让一种石头尽可能高的放。 最大值必须初始化为0因为存在高度为0的情况。 #includecstdio
#includecstring
#includealgorithm
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,Arrn);//按最高限度从小到大排序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)Mdp[i];printf(%d\n,M);}return 0;
}转载于:https://www.cnblogs.com/LUO257316/archive/2012/08/18/3220839.html
