P1417 烹调方案【泛化物品背包】

题目背景

由于你的帮助，火星只遭受了最小的损失。但gw懒得重建家园了，就造了一艘飞船飞向遥远的earth星。不过飞船飞到一半，gw发现了一个很严重的问题：肚子饿了~

gw还是会做饭的，于是拿出了储藏的食物准备填饱肚子。gw希望能在T时间内做出最美味的食物，但是这些食物美味程度的计算方式比较奇葩，于是绝望的gw只好求助于你了。

题目描述

一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。

众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大

输入格式

第一行是两个正整数T和n，表示到达地球所需时间和食材个数。

下面一行n个整数，ai

下面一行n个整数，bi

下面一行n个整数，ci

输出格式

输出最大美味指数

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

说明/提示

【数据范围】

对于40%的数据1<=n<=10

对于100%的数据1<=n<=50

所有数字均小于100,000

【题目来源】

tinylic改编

思路

　　第一眼觉得是一个01背包问题，写了写过了样例，但是只能过6个点。

　　然后发现由于时间不同，实际上每个物品的价值也会受到影响。

　　一种物品在不同的时间上可以看作是多种物品。

　　可以用数学归纳法证明：

假设对于相邻的两个时间点x和y 分别有两种不同的价值 若先选x(也就是后选y，t[x]=t+c[x],t[y]=t+c[x]+c[y]): v1=a[x]-(t+c[x])*b[x]+a[y]-(t+c[x]+c[y])*b[y] 若先选y： v2=a[y]-(t+c[y])*b[y]+a[x]-(t+c[y]+c[x])*b[x] 假定先选x价值大 将v1、v2去括号展开，相减 最终得到：c[y]*b[x]>c[x]*b[y];

　　由此，保证了取得局部最优解的情况下进行01背包，就可以求解出答案了

CODE

   #include    <   bits/stdc++.h   >  
   #define    dbg(   x   ) cout    <<    #x    <<    "   =   "    << x    << endl  
   #define    eps    1   e   -   8  
   #define    pi    acos(   -   1.0   )  

   using    namespace std   ;  
   typedef    long    long LL   ;  

   const    int inf    =    0x   3f3f3f3f   ;  

   template   <   class T   >   inline    void    read(T    &   res   )  
   {  
          char c   ;T flag   =   1   ;  
          while((c   =   getchar())   <   '   0   '   ||c   >   '   9   '   )if(c   ==   '   -   '   )flag   =-   1   ;res   =c   -   '   0   '   ;  
          while((c   =   getchar())   >=   '   0   '   &&c   <=   '   9   '   )res   =res   *   10   +c   -   '   0   '   ;res   *=flag   ;  
   }  

   namespace _buff    {  
          const    size_t BUFF    =    1    <<    19   ;  
          char    ibuf   [BUFF   ],    *ib    = ibuf   ,    *ie    = ibuf   ;  
          char    getc()    {  
              if    (ib    == ie   )    {  
               ib    = ibuf   ;  
               ie    = ibuf    +    fread(ibuf   ,    1   , BUFF   , stdin   );  
              }  
              return ib    == ie    ?    -   1    :    *ib   ++   ;  
          }  
   }  

   int    qread()    {  
          using    namespace _buff   ;  
          int ret    =    0   ;  
          bool pos    =    true   ;  
          char c    =    getc();  
          for    (;    (c    <    '   0   '    || c    >    '   9   '   )    && c    !=    '   -   '   ; c    =    getc())    {  
              assert(   ~c   );  
          }  
          if    (c    ==    '   -   '   )    {  
           pos    =    false   ;  
           c    =    getc();  
          }  
          for    (; c    >=    '   0   '    && c    <=    '   9   '   ; c    =    getc())    {  
           ret    =    (ret    <<    3   )    +    (ret    <<    1   )    +    (c    ^    48   );  
          }  
          return pos    ? ret    :    -ret   ;  
   }  

   const    int maxn    =    1   e   5    +    7   ;  

   int T   , n   ;  

   struct node    {  
       LL a   , b   , c   ;  
   }    v   [maxn   ];  

   LL    f   [maxn   ];  

   bool    cmp(node    x   , node    y   )    {  
          return    x   .   b    *    y   .   c    >    y   .   b    *    x   .   c   ;  
   }  

   int    main()  
   {  
          read(T   );  
          read(n   );  
          memset(f   ,    -   1   ,    sizeof   (f   ));  
          f   [   0   ]    =    0   ;  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              read(   v   [i   ].   a   );  
          }  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              read(   v   [i   ].   b   );  
          }  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              read(   v   [i   ].   c   );  
          }  
       LL ans    = INT_MIN   ;  
          sort(v    +    1   , v    + n    +    1   , cmp   );  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              for    (    int j    = T   ; j    >=    v   [i   ].   c   ;    --j    )    {  
                  f   [j   ]    =    max(   f   [j   ],    f   [j    -    v   [i   ].   c   ]    +    v   [i   ].   a    -    (LL   )j    *    v   [i   ].   b   );  
               //ans = max(f[j], ans);  
              }  
          }  
          for    (    int i    =    0   ; i    <= T   ;    ++i    )    {  
           ans    =    max(ans   ,    f   [i   ]);  
          }  
       cout    << ans    << endl   ;  
          return    0   ;  
   }  