3.1.6 Stamps 邮票

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

示例输出:

13

提示:

参考答案(内存最优[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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注