洛谷P1417 烹调方案【dp】-白红宇

洛谷P1417 烹调方案【dp】

阅读量：4356 次

发布时间：2019-06-07

本文共 1597 字，大约阅读时间需要 5 分钟。

题目：https://www.luogu.org/problemnew/show/P1417

题意：

一道菜有$a,b,c$三个值。烧一道菜的时间是$c$。得到的价值是，$a-t*b$其中$t$是菜完成的时间。

问用总时间t可以烧多少菜使得总价值最大。

思路：

很容易可以想到背包，一道菜做或是不做。

即$dp[t][i] = max(dp[t][i-1], dp[t-c_i][i-1]+a_i-t*b_i)$

但是由于$t$会影响到菜的价值，也就是说菜的顺序也是有影响的。所以并不是简单的背包。

考虑两道菜$x,y$，分别考虑先做$x$和先做$y$的情况，所得到的价值分别是：

$a_x-t*b_x+a_y-(t+c_x)*b_y$和$a_y-t*b_y+a_x-(t+c_y)*b_x$，可以发现这里可以贪心。

也就是如果$c_x*b_y > c_y*b_x$那么x在前可以得到更大的价值。按着个排个序再进行背包。

1 #include
     
       2 #include
      
        3 #include
        4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 13 #define inf 0x7fffffff14 using namespace std;15 typedef long long LL;16 typedef pair
                
                  pr;17 18 int n, t;19 const int maxn = 55;20 const int maxt = 100005;21 struct node{22 LL a, b, c;23 }food[maxn];24 LL dp[maxt][maxn];25 26 bool cmp(node a, node b)27 {28 return a.c * b.b < b.c * a.b;29 }30 31 int main()32 {33 scanf("%d%d", &t, &n);34 for(int i = 1; i <= n; i++){35 scanf("%lld", &food[i].a);36 }37 for(int i = 1; i <= n; i++){38 scanf("%lld", &food[i].b);39 }40 for(int i = 1; i <= n; i++){41 scanf("%lld", &food[i].c);42 }43 sort(food + 1, food + 1 + n, cmp);44 45 for(int i = 1; i <= n; i++){46 for(int j = t; j >= 0; j--){47 if(j >= food[i].c)dp[j][i] = max(dp[j][i - 1], dp[j - food[i].c][i - 1] + food[i].a - (j) * food[i].b);48 else dp[j][i] = dp[j][i - 1];49 }50 }51 LL ans = 0;52 for(int j = 0; j <= t; j++){53 ans = max(ans, dp[j][n]);54 }55 printf("%lld\n", ans);56 57 return 0; 58 }