WZK的减肥计划

WZK 的减肥计划(plan.cpp/ plan.in/ plan.out)
问题描述：
WZK 发现他的体重正迅猛的上升着，对此他感到非常焦虑，想要制定出一套完美的减肥计划。

于是 WZK 翻阅资料，查到了各种食品所含的卡路里和价格，并且千辛万苦的测出了自己一天所需的卡路里。
现在有 n 种食品可供 WZK 选择，每种物品都有给定的价格，卡路里和拥有数量，你的任务就是要选出一些食品使得总卡路里大于消耗量且最小，如果有多种组合满足条件，则取价格最小的。
输入格式：
第一行为两个整数 n(0<n<=100)， k（0<k<=10^5）分别表示物品个数和一天消耗的最少卡路里。
接下来 n 行每行 3 个整数， costi， mi， cali（ 0< costi,cali<10^6,1<=mi<=100）分别表示价格，数量和所含卡路里。
输入数据保证合法、有解。
输出格式：
满足条件的总卡路里和总价格，中间用一个空格隔开。
注意：保证答案的总卡路里小于 10^5，总价格小于 10^8。
输入样例：
5 10
10 2 6
5 1 9
6 1 6
9 1 6
5 1 9
输出样例：
12 15

写循环的时候一直有不祥的预感

但是因为这次题目都还蛮简单所以就非常笨蛋地安慰了自己

不知道出于什么样的心理也没检查剩下的时间就在题目的pdf文件上乱画画

然后果然这题就差点爆零了呢...

反省！

下次绝对认真画

重写的时候发现其实是二进制分割物品写错了...

一直担心的循环反而神奇地没写错

哈哈哈？？？

而且倒序循环的时候范围又开大了所以还会超时

可能等输入完数据统计最大卡路里再来循环会优化一些

不过我就懒得写了

 #include<bits/stdc++.h>

 using namespace std;

 int n , k , a , b , c , all;

 int minn =  , ans =  ;

 int f[] ;

 int read(){

     char c ;

     int sign =  ;

     while((c = getchar())<''|| c >'')

         if(c=='-') sign = - ;

     int Ans = c - '' ;

     while((c = getchar())>=''&& c<='')

         Ans = Ans *  + c - '' ;

     return Ans * sign ;

 }

 void deal(int a , int b){

     for(int i =  ; i >= b ; -- i){

         if(f[i] > a + f[i - b]) {

             f[i] = a + f[i - b] ;

             if(i > k && ( i < ans || (i == ans && f[i] < minn)))

                 ans = i , minn = f[i] ;

             }

     }

 }

 int main(){

     //freopen("plan.in","r",stdin);

     //freopen("plan.out","w",stdout);

     n = read() , k = read() ;

     for(int i =  ; i <=  ; ++ i)

         f[i] = ;

     f[] =  ;

     for(int i =  ; i <= n ; ++ i){

         a = read() , b = read() , c = read() ;

         int two =  ;

         while((b -= two) >= ){

             deal(two * a , two * c) ;

             two = (two<<)  ;

         }

         b += two ;

         if(b != ){

             deal(b * a , b * c) ;

         }

     }

     cout << ans << ' ' << minn ;

     return  ;

 }

巴特西

WZK的减肥计划

最新文章

热门文章