3.1.6 Stamps 邮票

code

6 年前

3.1.6 Stamps 邮票

时间： 1ms 内存：64M

描述：

已知一个 N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限 K —— 表示信封上能够贴 K 张邮票。计算从 1 到 M 的最大连续可贴出的邮资。

例如，假设有 1 分和 3 分的邮票；你最多可以贴 5 张邮票。很容易贴出 1 到 5 分的邮资（用 1 分邮票贴就行了），接下来的邮资也不难：

6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1。
然而，使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资。因此，对于这两种邮票的集合和上限 K=5，答案是 M=13。

输入：

第 1 行：两个整数，K 和 N。K（1 <= K <= 200）是可用的邮票总数。N（1 <= N <= 50）是邮票面值的数量。第 2 行 .. 文件末： N 个整数，每行 15 个，列出所有的 N 个邮票的面值，面值不超过 10000。

输出：

第 1 行：
一个整数，从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。

示例输入：

5 2
1 3

示例输出：

提示：

参考答案（内存最优[8904]）：

# include<stdio.h>//DP,多重背包
# define M 9999999
int sign[55],f[2000005];
int min(int a,int b)
{
    return (a<b?a:b);
}
int main()
{
    int num,n,i,j;
    scanf("%d %d",&num,&n);
    for(i=0;i<n;i++)
        scanf("%d",&sign[i]);
    f[0]=0;
     for(i=1;;i++)
     {
         f[i]=M;
         for(j=0;j<n;j++)
            if(sign[j]<=i)     
            f[i] = min(f[i],f[i-sign[j]]+1);  
        if(f[i]>num)//如果最小的数目都超过了num，那这个i就一定贴不出  
        break;  
     }   
     printf("%d\n",i-1);   
     return 0;
}

参考答案（时间最优[620]）：

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 2000002
int ans[MAX];
int num[51];
int main()
{
	int k,n,i,j,big;
	cin>>k>>n;
	big=0;
	for(i=0;i<n;i++)
	{
		cin>>num[i];
		if(num[i]>big)big=num[i];
	}
	if(big==1)
	{
		cout<<k<<endl;
		return 0;
	}
	memset(ans,1,sizeof(ans));
	ans[0]=0;
	for(i=1;i<=k;i++)
		ans[i*big]=i;
	for(i=1;i<=MAX;i++)
	{
		if(i%big==0)continue;
		for(j=0;j<n;j++)
			if(i-num[j]>=0)
			  if(ans[i-num[j]]+1<ans[i])ans[i]=ans[i-num[j]]+1;
	    if(ans[i]>k)break;
	}
	cout<<i-1<<endl;
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。