原题地址：http://codeforces.com/contest/788/problem/C

题意大致是这样的：

你有k个种类的可口可乐，每瓶的二氧化碳浓度为$a_i/1000$（每瓶有无限个，$a_i$是正整数，可以相同）

你需要调配出浓度为$n/1000$（n也是正整数）的可口可乐

二氧化碳浓度为二氧化碳体积除以可口可乐总体积

$1≤k≤1e6，0≤n≤1000，0≤a_i≤1000$

很明显一开始都会这么想：

首先套路地将$a_i$减去$n$，接着我们就是要让选出来的可乐浓度和为0

因为每种浓度有无限瓶，那么就可以去重了，k就缩到了1000。

所以接下来我们就可以考虑背包：

我们将$a_i$分成大于0和小于0的（有等于0的就做完了）

分别dp在f数组和g数组里。

就是这样：

memset(f, 63, sizeof f);
memset(g, 63, sizeof g);
f[0] = g[0] = 0;
for(int i = 1; i <= k; i++) {
    if(a[i] < 0) {
        for(int j = -a[i]; j <= 1000000; j++)
            f[j] = std::min(f[j], f[j+a[i]]+1);
    } 
    if(a[i] > 0) {
        for(int j = a[i]; j <= 1000000; j++)
            g[j] = std::min(g[j], g[j-a[i]]+1);
    }
}

接着对所有的f[x]+g[x]中找最小的就好了。

复杂度O(k*1000*1000)，k即使是1000也是过不了的。

然后正解大致是枚举答案，bitset来优化dp。

但是我的思路却奇怪了：

我想，如果可乐的浓度种类数很多，那么在答案取到最小值的时候，背包的容量也不会很大，因为浓度可以说非常的挤，于是我打算让上界不固定。

memset(f, 63, sizeof f);
memset(g, 63, sizeof g);
f[0] = g[0] = 0;
for(int i = 1; i <= k; i++) {
    if(a[i] < 0) {
        for(int j = -a[i]; j <= 1000000/k; j++)
            f[j] = std::min(f[j], f[j+a[i]]+1);
    } 
    if(a[i] > 0) {
        for(int j = a[i]; j <= 1000000/k; j++)
            g[j] = std::min(g[j], g[j-a[i]]+1);
    }
}

复杂度O(1000000)

接着交上去就过了。

看了一下过的人发现好像只有我一个人是这种做法

但是我不能证明这个做法的正确性，或者，如果是错的，各位能不能卡掉。