原题地址：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)

接着交上去就过了。

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

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

第一篇uoj博客～

相信很多同学都喜欢cin,cout的方便，却因为cin,cout的常数太大而常常弃之不用，所以经常会写上输入输出优化，很多同学甚至嫌输入输出优化麻烦直接用scanf,printf了

所以我的这个模板强行把常数小的fread,fwrite套在了结构体里，并给结构体赋予了>>，<<运算符，常数方便两不误！（当然是指刷题）

因为为了代码的整齐度之类的（写的比较全，强迫症），并没有去搞什么更奇技淫巧的优化了，所以常数可能相对于大神来说，会偏大？？？

特别地，我的浮点数输入对于1e-6，2.1e-3这种能够接受，为什么呢？因为一次模拟赛，出题人卡输入的常数，结果又是用cout造的数据，什么意思？你们可以尝试一下

std::cout<<0.0000001<<std::endl;

然后我那天一直以为被卡精度，结果（mmp）。。。。于是我在板子上加了这个。

总的来说有以下优点：

1.使用方便（对于喜爱文件读入读出的同学更开心了，喜爱控制台的可就不那么好接受了--）//什么你觉得断点输出很麻烦？SF会查不出来？试试cerr吧！

2.速度客观 略快于一般的getchar的读入优化（常数大师的除外，常数大师可能不用getchar吧？），远快于std的cin,cout

3.输入输出较为齐全，适用于绝大部分题目

4.支持多文件输入，你可以直接用FILE *fp = fopen 打开一个新的文件然后io::filein fin(fp); fin.in()就好啦！是不是很方便呢

有以下缺点：

1.double,float的输出不够优美，我是用sprintf的，因为单单的写四舍五入乘法除法浮点数的效率已经和printf差不了多少了，所以直接上了sprintf，速度还是灰常快滴（你同样也可以用cout.bit(x)来将其改为保留小数点后x位）

2.不支持long double的输出（感觉也很少用。。。其实是我不是很会写...0.0）

希望各路大神不喜勿喷，喜欢的同学可以拿去尝试一下，有什么意见和bug可以在评论区告诉我，谢谢。

更新: 2017.8.18 内容：将文件内置于两个结构体中，并通过一个宏变量LOCAL来决定是否打开文件，从本地交题到OJ上请删除或者注释掉#define LOCAL

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <complex>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define rep(i, a, b) for(rg int (i) = (a), __omega = (b); (i) <= __omega; ++(i))
#define down(i, a, b) for(rg int (i) = (a), __omega = (b); (i) >= __omega; --(i))
#define run(x) for(rg int __omega = (x); __omega; --__omega)

#define cmax(i, j) ((i) < (j) ? (i) = (j) : (i))
#define cmin(i, j) ((i) > (j) ? (i) = (j) : (i))
#define dmax(i, j) ((j) < (i) ? (i) : (j))
#define dmin(i, j) ((i) < (j) ? (i) : (j))
#define dabs(i) ((i) > 0 ? (i) : -(i))
#define cabs(i) ((i) < 0 ? (i) = -(i) : (i))
#define dsqr(i) ((i)*(i))

#define rg register
#define int64 long long
#define uint unsigned int
#define uint64 unsigned long long

namespace io {

    const int IO_size = 1<<25;

    struct filein {

        char B[IO_size], *S;
        FILE *file;

        inline void operator = (rg FILE *f) { file = f; }
        filein(FILE *f = NULL) { S = B; if(f) *this = stdin; }
        void setfile(const char *filename) { file = fopen(filename, "r"); in(); }
        void closefile() { fclose(file); }
        inline void in() { fread(B, 1, IO_size, file); }

        template<typename type>
        inline type read_int() {
            rg type aa; rg char cc;
            for(; (*S < 48 || *S > 57) && *S != '-'; S++);
            cc = *S == '-' ? (S++, 0) : 1, aa = *S++-48;
            for(; *S >= 48 && *S <= 57; S++) aa = (aa<<1)+(aa<<3)+*S-48;
            cc ? : aa = -aa; return aa;
        }

        template<typename type>
        inline type read_float() {
            rg type aa, bb = 0, gg = 1; rg char cc;
            rg char ch;
            for(; (*S < 48 || *S > 57) && *S != '-'; S++);
            cc = *S == '-' ? (S++, 0) : 1, aa = *S++-48;
            for(; *S >= 48 && *S <= 57; S++) aa=aa*10+*S-48;
            if(*S == 'e') {
                bb += aa; aa = 0;
                S++; int k = read_int<int>();
                if(k < 0) while(k) bb /= 10, k++;
                else while(k) bb *= 10, k--;
            }
            if(*S == '.') {
                for(S++; *S >= 48 && *S <= 57; S++)
                    bb += (*S-48)*(gg /= 10);
                if(*S == 'e') {
                    bb += aa; aa = 0;
                    S++; int k = read_int<int>();
                    if(k < 0) while(k) bb /= 10, k++;
                    else while(k) bb *= 10, k--;
                }
            }
            aa += bb, cc ? : aa = -aa;
            return aa;
        }

        inline char getc() { return *S++; }
        inline void gets(rg char *s) {
            for(; *S == ' ' || *S == '\n'; S++);
            for(; *S != ' ' && *S != '\n' && ~*S && *S; *s++ = *S++);
            *s++ = '\0';
        }

    } cin(stdin);

    struct fileout {

        char U[IO_size], *O, bit_float[20], bit_double[20];
        FILE *file;

        inline void operator = (rg FILE *f) { file = f; }
        fileout(FILE *f = NULL) { O = U; bit(6); if(f) *this = f;}
        void setfile(const char *filename) { file = fopen(filename, "w"); }
        void closefile() { out(); fclose(file); }
        inline void out() { fwrite(U, 1, O-U, file), O = U; }

        template<typename type>
        inline void write(rg type a) {
            static char stack[50];
            rg int i = 0;
            if(!a) { *O++ = 48; return; }
            a < 0 ? a = -a, *O++ = '-' : 1;
            for(; a; a /= 10) stack[++i] = a%10;
            for(; i; *O++ = stack[i--]+48);
        }

        inline void bit_f(rg int len) {
            rg char *it = bit_float;
            *it++ = '%', *it++ = '.';
            if(len > 9) *it++ = len/10+48, *it++ = len%10+48;
            else *it++ = len+48;
            *it++ = 'f';
            *it++ = '\0';
        }

        inline void bit_d(rg int len) {
            rg char *it = bit_double;
            *it++ = '%', *it++ = '.';
            if(len > 9) *it++ = len/10+48, *it++ = len%10+48;
            else *it++ = len+48;
            *it++ = 'l', *it++ = 'f';
            *it++ = '\0';
        }

        inline void bit(rg int len) { bit_f(len), bit_d(len); }
        inline void write_float(rg float a) { O += sprintf(O, bit_float, a); }
        inline void write_double(rg double a) { O += sprintf(O, bit_double, a); }
        inline void putc(rg char c) { *O++ = c; }
        inline void puts(rg const char *s) { for(; *s; s++) *O++ = *s; }

    } cout(stdout);

    inline filein& operator >> (rg filein& _in, rg int& x) { x = _in.read_int<int>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg int64& x) { x = _in.read_int<int64>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg uint& x) { x = _in.read_int<uint>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg uint64& x) { x = _in.read_int<uint64>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg char& ch) { ch = _in.getc(); return _in; }
    inline filein& operator >> (rg filein& _in, rg char *s) { _in.gets(s); return _in; }
    inline filein& operator >> (rg filein& _in, rg float& x) { x = _in.read_float<float>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg double& x) { x = _in.read_float<double>(); return _in; }
    inline filein& operator >> (rg filein& _in, rg long double& x) { x = _in.read_float<long double>(); return _in; }

    inline fileout& operator << (rg fileout& _out, rg int x) { _out.write<int>(x); return _out; }
    inline fileout& operator << (rg fileout& _out, rg int64 x) { _out.write<int64>(x); return _out; }
    inline fileout& operator << (rg fileout& _out, rg uint x) { _out.write<uint>(x); return _out; }
    inline fileout& operator << (rg fileout& _out, rg uint64 x) { _out.write<uint64>(x); return _out; }
    inline fileout& operator << (rg fileout& _out, rg char ch) { _out.putc(ch); return _out; }
    inline fileout& operator << (rg fileout& _out, rg const char *s) { _out.puts(s); return _out; }
    inline fileout& operator << (rg fileout& _out, rg float x) { _out.write_float(x); return _out; }
    inline fileout& operator << (rg fileout& _out, rg double x) { _out.write_double(x); return _out; }

    const char endl = '\n';
}

namespace work_space {

    #define LOCAL

    using namespace io;

    void main() {
        rg int a, b;
        cin >> a >> b;
        cout << a+b << endl;
    }

}

#ifdef LOCAL
#define setfile(s) io::cin.setfile(s".in"), io::cout.setfile(s".out")
#define closefile() io::cin.closefile(), io::cout.closefile()
#else
#define setfile(s) io::cin.in()
#define closefile() io::cout.out()
#endif
#define filename "data"

int main() {
    setfile(filename);
    work_space::main();
    closefile();
    return 0;
}