usaco_stamps.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:stamps
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cstring>
#include <memory>
#include <algorithm>
#define cin fin
using namespace std;
const int Maxint=10000000;
ifstream fin("stamps.in");
ofstream fout("stamps.out");
int main()
{
    int f[2000001];
    int v[201];
    int i,j,k,n,m,maxnum=0;
    cin>>k>>n;
    for(i=0;i<n;i++) {cin>>v[i]; if(v[i]>maxnum) maxnum=v[i];}
   // sort(v,v+n);
	memset(f,0,sizeof(f));
    for(i=1;i<=maxnum*k;i++)
    {  f[i]=Maxint;
       for(j=0;j<n;j++){
          if(i<v[j]) continue;
          if(f[i]>f[i-v[j]]+1) f[i]=f[i-v[j]]+1;
       }
       if(f[i]>k && f[i]!=Maxint) break;
    }
    fout<<i-1<<endl;
//	system("PAUSE");
    return 0;
}