做题感悟:这题类似以前做过的一题,那一题的体积也很大,开数组开不下,物品只有三件,先贪心一下,然后完全背包,这题因为物品很多不能那样。
解题思路:转自~~>
先把剪枝放在这里,设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 ; }