学步园

第一次做usaco，别人推荐我做的。一个完全背包是否能装满的问题，不习惯那里的输入输出。

不过最后还是A了，感觉usaco挺好的，有时间一定要去全都做完。

下面是代码：

/*
ID: sunexio2
PROG: stamps
LANG: C++
*/


#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

bool f[2001000];
int ff[2001000];

int cmp(const void *a, const void *b)
{
    int *c, *d;
    c = (int *)a;
    d = (int *)b;
    return *c - *d;
}


int main()
{
    int K, N;
	ofstream fout ("stamps.out");
    ifstream fin ("stamps.in");
    while(fin >> K >> N)
    {
        int m[60] = {0};
        for(int i = 0; i < N; ++i)
            fin >> m[i];
        qsort(m, N, sizeof(int), cmp);
		memset(f, 0, sizeof(f));
		memset(ff, 0, sizeof(ff));
		f[0] = 1;
        for(int i = 0; i < N; ++i)
        {
			int kk = K * m[i] - m[i];
            for(int j = 0; j <= kk; ++j)
            {
			     if(ff[j] < K && f[j] == 1)
                 {
                    if(f[j + m[i]])
                        ff[j + m[i]] = ff[j + m[i]] > ff[j]? ff[j] + 1 : ff[j + m[i]];
					else
					{
						f[j + m[i]] = 1;
						ff[j + m[i]] = ff[j] + 1;
					}
                 }
            }
        }
        int i;
        for(i = 0; ;  )
        {
            if(f[i])
                ++i;
            else
                break;
        }
        fout << i - 1 << endl;
    }
    return 0;
}