2014年1月24日 星期五

[USACO] 3-1-6 Stamps


/*
ID: 551100k1
LANG: C++
TASK: stamps
*/
#include<stdio.h>
#include<queue>
using namespace std;
queue<int> que,tmp;
int s[2000005]={0};
int r[205];
int main(){
    freopen("stamps.in","r",stdin);
    freopen("stamps.out","w",stdout);
    int n,m,i,j,a,b,p;
    scanf("%d%d",&n,&m);
    que.push(0);
    s[0]=1;
    for(i=0;i<m;i++)
        scanf("%d",&r[i]);
    for(i=0;i<n;i++){
        tmp=que;
        while(que.size()) que.pop();
        while(tmp.size()){
            p=tmp.front();
            tmp.pop();
            for(j=0;j<m;j++){
                if(s[p+r[j]]==0){
                    s[p+r[j]]=1;
                    que.push(p+r[j]);
                }
            }
        }
    }
    for(i=1;i<=2000000;i++)
        if(s[i]==0)
            break;
    printf("%d\n",i-1);
}

沒有留言:

張貼留言