NYOJ 248 BUYING FEED

题目链接~~>

做题感悟：在比赛遇到这题本来是应该高兴的，但是做这题时剩下半个小时左右，时间是很充足（当时想到用多重背包解决），当时就不淡定了调试了好久也没调出来（写给不淡定的自己）。

解题思路：1)多重背包  这题一看就知道必须从后往前找（后面的不会对前面的造成影响），so 想到处理成多重背包，切记体积为重量。

                  2 ) 贪心  ( 很经典)  把每一点的单位重量从当前点到终点的总价值算出来（即：当前点的单位重量价值），那么只要排一下序单位价值从小到达依次贪心就可以。

代码（多重背包）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define lld __int64
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-4 ;
     
    
   

    

     

    
    

     

      const int  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX = 100005 ;
     
    
   

    

     

    
    

     

      int k,r,m,n,sum ;
     
    
   

    

     

    
    

     

      int w[MX],v[MX],dp[MX] ; // v[ ] 存体积 w[ ] 花费的价值
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,v,w ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      bool cmp(node a,node b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return a.x > b.x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void search(int dis,int num,int wx)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=num ;i=i<<1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       w[r++]=dis*i+i*wx ; 
     
    
   

    

     

    
    

     

       v[r-1]=i ;
     
    
   

    

     

    
    

     

       num-=i ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(num)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       w[r++]=dis*num+num*wx ;
     
    
   

    

     

    
    

     

       v[r-1]=num ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       dp[i]=INF ;
     
    
   

    

     

    
    

     

       dp[0]=0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&k,&m,&n) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 scanf("%d%d%d",&T[i].x,&T[i].v,&T[i].w) ;
     
    
   

    

     

    
    

     

       sort(T,T+n,cmp) ;
     
    
   

    

     

    
    

     

       sum=0  ;  r=0 ;
     
    
   

    

     

    
    

     
 int y ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++) // 多重背包二进制优化
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       y=m-T[i].x ;
     
    
   

    

     

    
    

     

       sum+=T[i].v ;
     
    
   

    

     

    
    

     

       search(y,T[i].v,T[i].w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       init() ; // 初始化
     
    
   

    

     

    
    

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

    

     

    
    

     
 for(int j=sum ;j>=v[i] ;j--)
     
    
   

    

     

    
    

     
 if(dp[j]>dp[j-v[i]]+w[i])
     
    
   

    

     

    
    

     

       dp[j]=dp[j-v[i]]+w[i] ;
     
    
   

    

     

    
    

     
 int min=INF ;
     
    
   

    

     

    
    

     
 for(int i=k ;i<=sum ;i++) // 寻找最优解
     
    
   

    

     

    
    

     
 if(min>dp[i])
     
    
   

    

     

    
    

     

       min=dp[i] ;
     
    
   

    

     

    
    

     
 printf("%d\n",min) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（贪心）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define lld __int64
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const double esp = 1e-4 ;
     
    
   

    

     

    
    

     

      const int  md= 2810778 ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX = 100005 ;
     
    
   

    

     

    
    

     

      int k,r,m,n,sum ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int v,w ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      bool cmp(node a,node b) // 按价值小排序
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return a.w < b.w ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&k,&m,&n) ;
     
    
   

    

     

    
    

     
 int x,y ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&x,&T[i].v,&y) ;
     
    
   

    

     

    
    

     

       T[i].w = m-x + y ; // 处理单价
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(T,T+n,cmp) ;
     
    
   

    

     

    
    

     
 int best=0 ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++) // 从单价小的开始贪心
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(T[i].v>=k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       best+=k*T[i].w ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       k-=T[i].v ;
     
    
   

    

     

    
    

     

       best+=T[i].v*T[i].w ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",best) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/23418973