> 写了个思想：欢迎提供一下意见！
> 
> 解题思想与上界证明：
> 
> 题意是：有一些酒，和一些酒瓶，需要用酒瓶来装这些酒，但是装酒瓶时，每瓶不能太满也不能十分不满，满的话受热膨胀会挤出瓶塞，太少的话，空气就多，酒就会变质。现在希望把酒装进酒瓶后剩下的酒最少，求这个最少值！酒的量十分大：1000000000（10亿）
> 一道有一个剪枝的背包DP。
> 
> 剪枝方法：
> 
> 可以想象 ，给出酒的量太大了，即使是线性时间运行都会超时！
> 想象一下，它可能是量大到一定的时候是一定一点不剩的！那么什么是其最大值呢！
> 其实最大值为450000就足够了！ 证明如下
> 
> 现假设有很多很多的酒，那么它肯定能装满很多瓶，可能有一瓶是剩余的！（概率十分大）假设剩余约为0%（其实是不能等于0%的，否则就是刚好装到一点不剩的状态，约为0%是最坏的情况），那么就可以从那些满的状态把酒给那个只有一点酒的瓶子中，最坏的情况是可以把1%酒给它，那么至少需要这样的满瓶是99瓶！所以，上界值就是  ：  99*Max(L)+1  （加1是因为那瓶酒剩1ml，这是最坏情况）。这里的最满是4500ml，那么代入公式：
> 99*4500+1=445501.上界为445501 。其实上界可以根据实际给出的数字求出来的，这样的剪枝就更好了！能更省时间！
> 
> 然后就是DP了！
> 枚举最大和最小值背包DP，就行了！然后加一个
> 	int tap=0;
> 	for (i=0;i<n;i++)
> 	{
> 		for (j=minl[i];j<=maxl[i];j++)
> 		{
> 			if(dp[j])
> 			{
> 				tap=1;
> 				break;
> 			}
> 		}
> 		if(tap) break;
> 	}
> 就可以AC了！ 可以证明为什么只枚举最大和最小值。
> 可以想象两种情况：
> 1.一定有剩余的情况，那么有一个瓶是少于下界值的，其他的瓶都是最满的.
> 2.假设刚好装下。那么就可以把一些大于某些瓶上界的酒移到，快全满的酒瓶中，一直移，最终能达到，一些瓶是全满的，一些瓶是刚好满的，一个瓶介于最满与最不满之间。对于这个瓶，通过上面的两重循环就可以判断。其他最满和最不满枚举最大和最小值的背包DP就行了。
> 
> 
> 

• Re:此题好的做法是dijkstra (17) 1272406003 2009-10-06 10:29:39