UVA 10280 - Old Wine Into New Bottles

题目总结~~>

做题感悟：这题类似以前做过的一题，那一题的体积也很大，开数组开不下，物品只有三件，先贪心一下，然后完全背包，这题因为物品很多不能那样。

解题思路：转自~~>

      先把剪枝放在这里，设limit=min{max*min/(max-min)}，那么如果酒量是大于limit的，就必然能够全部装下，否则我们再执行dp。
     下面我们开始证明这个剪枝的正确性。我们不妨先对一类瓶子进行讨论，设其最小、最大的装酒量分别是min、max，实际上如果有[x/max]<[x/min]，那么酒量x就一定可以全部被装进去，因为满足min*[x/min]<=x<=max*[x/min]，必然可以找到一点x’使得x’*[x/min]==x，其中方括号都是向下取整运算。我们不妨设x/max的小数部分是e1，x/min的小数部分是e2，如果有[x/max]<[x/min]，即为x/max-e1<x/min-e2，整理得x/max-x/min<e1-e2，同时由于-1<e1-e2，所以如果x/max-x/min<=-1，那么原不等式必然成立，进一步化简就可以得到x>=max*min/(max-min)。
     其实，看了别人的一篇博客后，发现可以用更简单的方式去证，同时还能使剪枝更强。同样，先把剪枝放在这里，limit=min{min*min/(max-min)}。
     对于一类瓶子，我们不妨设用k个瓶子去装酒，那么能够完全装下的范围就是[k*min,k*max]，随着k的增大，我们发现所有相邻区间的左端点的间距是固定的，同时区间的长度又在不断增加，于是我们猜想，到某一刻时，后面的区间相互之间会有交集，这样剩下的各个区间就会覆盖掉后面所有的整数。我们设刚开始产生交集的区间为第k个，这样有k*max>=(k+1)*min，解得k>=min/(max-min)，而当酒量x>=k*min的时候，就一定能全被装进去，这样就有x>=min*min/(max-min)。
     最后说一说dp的过程吧，有了上面的剪枝，我们最起码能把总酒量的状态减到4500*4500，大约是2*10^7，剩下的工作就是把瓶子按不同的容积拆成max-min+1个瓶子，然后做完全背包的dp。这样我们不妨想一下，最后瓶子数乘上酒量的状态数会不会超呢？实际上由于min<=0.99max，所以即使容量是4500也实际只有不到450000个状态，远小于2*10^7，当然最大是否有可能超过450000而且最大是多少还要根据剪枝的函数来确切算一下，而且我们dp前是可以把体积重复的瓶子去掉的，由于判重的剪枝瓶子数最后能不能到比较大的水平也是个问题，所以整体的复杂度受多方因素的制约。
     就剪枝min*min/(max-min)来讲，由于min*min/(max-min)<=min*min/(min/0.99-min)<450000，所以最多不会超过450000个状态。

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const int INF = 9999999 ;
     
    
   

    

     

    
    

     

      const int mod = 1e9 + 7 ;
     
    
   

    

     

    
    

     

      const int MY = 100 + 10 ;
     
    
   

    

     

    
    

     

      const int MX = 450000 + 10 ;
     
    
   

    

     

    
    

     

      int n ,C ,LC ,num ;
     
    
   

    

     

    
    

     

      bool vis[4500] ;
     
    
   

    

     

    
    

     

      int dp[MX] ,mx[MY] ,my[MY] ,V[MX]  ;
     
    
   

    

     

    
    

     

      void solve()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 scanf("%d%d" ,&C ,&n) ;
     
    
   

    

     

    
    

     

       C *= 1000 ;
     
    
   

    

     

    
    

     

       LC = INF ;
     
    
   

    

     

    
    

     

       num = 0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d" ,&mx[i] ,&my[i]) ;
     
    
   

    

     

    
    

     
 if(mx[i]*mx[i] / (my[i]-mx[i]) < LC)
     
    
   

    

     

    
    

     

       LC = mx[i]*mx[i] / (my[i]-mx[i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(C >= LC)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<"0"<<endl ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 memset(vis ,false,sizeof(vis)) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 for(int j = mx[i] ;j <= my[i] ;++j)
     
    
   

    

     

    
    

     
 if(!vis[j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[j] = true ;
     
    
   

    

     

    
    

     

       V[num++] = j ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 memset(dp ,0 ,sizeof(dp)) ;
     
    
   

    

     

    
    

     

       dp[0] = 0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 for(int j = V[i] ;j <= C ; ++j)
     
    
   

    

     

    
    

     

       dp[j] = max(dp[j] ,dp[j-V[i]] + V[i]) ;
     
    
   

    

     

    
    

     
 cout<<C-dp[C]<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx ;
     
    
   

    

     

    
    

     
 scanf("%d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       solve() ;
     
    
   

    

     

    
    

     
 if(Tx)  cout<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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