题解 P2725 【邮票 Stamps】

「QQ红包」 · 2017-07-04 15:37:18 · 题解

完全背包，然后从头搜就可以了，

具体见代码

/*
ID: redbag
PROG: stamps 
LANG: C++     
*/
#include<set>  
#include<map>  
#include<list>  
#include<queue>  
#include<stack>  
#include<string>  
#include<math.h>  
#include<time.h>  
#include<vector>  
#include<bitset>  
#include<memory>  
#include<utility>  
#include<stdio.h>  
#include<sstream>  
#include<iostream>  
#include<stdlib.h>  
#include<string.h>  
#include<algorithm> 
#define LL unsigned long long   
using namespace std;
int k,n,i,j,s,a;//k:总共消耗的邮票数 
int f[2000000];//f[i]表示构成面值为i至少需要的邮票数 
int main() 
{
    scanf("%d%d",&k,&n);
    for (i=1;i<=2000000;i++) f[i]=2333;//标记
    f[0]=0;//赋初值 ，用0张邮票可以构成0
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a);//读入 
        for (j=a;j<=2000000;j++)
        if (f[j-a]+1<=k)//用的邮票数目在范围内 
            f[j]=min(f[j],f[j-a]+1);//取较小的 
    } 
    s=0;
    for (i=1;i<=2000000;i++)//找从1开始 连续 的能取的集合的最后一个。 
        if (f[i]==2333)//凑不出了 
        {
            s=i-1;//记录 
            break;//退出 
        }
    printf("%d\n",s);//输出 
    return 0;
}