understand for CodeForces 526C bag
unravel: 解开
cohort: 所有
dilution: 稀释
ligation： 绑
contamination: 污染物
faecal: 排泄物
trim: 修剪，剪枝
agglomerative: 成块的
homogenous: 同质的
heterogenous: 多样的
undergo: 经历
protocol: 计划
aberrant: 异常的
concomitant: 伴随的
speculate: 推测
skew: 歪斜的
inherent: 固有的
markdown 乘号用\*
http://codeforces.com/contest/526/problem/C
输入w, w1, w2, v1, v2
求max(n1*v1+n2*v2)
st. w1*n1+w2*n2<=w, n1,n2=0,1,2…,
看起来是个简单的线性规划，但是用程序实现是有技巧的。
今天看了卓大神学弟的博客之后，完全理解了这题如何利用数学进行优化时间复杂度从O(W)到O(sqrt(W))
http://mycodebattle.com/2015/04/codeforces-526c/
首先保证w1,v1是性价比更高的包，
if(v1/w1<v2/w2) swap(1,2)
if(w1>=sqrt(C)), 则w/w1<=sqrt(C), 那么直接包1，枚举就好了，时间复杂度O(sqrt(C))
否则，选择包2进行枚举，i=1->min(w/w2, w1-1)
至于第二个条件i=1->min(w/w2, w1-1)的证明如下：
首先如果可以装w1个包2，那么币可以装w2个包1，因为总重量相等，w1*w2=w2*w1
因为保证了v1/w1>=v2/w2, v1w2>=v2w1, 如果选了w1个包2的话，那么全部换成w2个包1，重量不变，并且价值相等或增加，因此包2如果选的>=w1，
则存在有一个至少等值的解，其包2的个数<w1
int a[maxn], n, t, m;
int main()
{
/*
#ifndef ONLINE_JUDGE
freopen ("in.txt" , "r" , stdin);
freopen ("out.txt" , "w" , stdout);
#endif
*/
LL w, hr , hb, wr, wb;
while(cin>>w)
{
cin>>hr>>hb>>wr>>wb;
//if(double(hr)/wr<double(hb)/wb)
if(double(hr)/wr<double(hb)/wb) swap(hr, hb), swap(wr, wb);
LL maxv=0;
//int qw=sqrt(w)
if(wr*wr>w)
{
for(LL i=0;i<=w/wr;i++)
{
maxv=max(maxv, i*hr+(w-i*wr)/wb*hb);
}
}
else
{
for(LL i=0;i<=min(w/wb,wr-1);i++)
{
maxv=max(maxv, i*hb+(w-i*wb)/wr*hr);
}
}
cout<<maxv<<endl;
}
return 0;
}