题目描述 Description

给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤40)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1~MAX之间的每一个邮资值都能得到。

例如,N=3,K=2,如果面值分别为1分、4分,则在1分~6分之间的每一个邮资值都能得到(当然还有8分、9分和12分);如果面值分别为1分、3分,则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3,K=2时,7分就是可以得到的连续的邮资最大值,所以MAX=7,面值分别为1分、3分。

输入描述 Input Description

N和K

输出描述 Output Description

每种邮票的面值,连续最大能到的面值数。数据保证答案唯一。

样例输入 Sample Input

3 2

样例输出 Sample Output

1 3

MAX=7

动态规划加深搜,每枚举一种邮票面值为a[i]的邮票,可能有的最大值在a[i]+1到a[i]*k+1之间。思路是枚举所有可能的邮票组合方式,即枚举面值,分别求得每一种组合方式能得到连续最大能到的面值数,并记录当前的组合方式,就能不断更新这个最大面值数。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,maxn;
int a[];
int num[];
int ans[];
void dp()
{
int i=;
num[]=;
while(num[i]<=n)
{
i++;
num[i]=;
for(int j=;j<k&&i>=a[j];j++)
{
if(num[i-a[j]]+<num[i])
num[i]=num[i-a[j]]+;
}
}
if(i->maxn)
{
maxn=i-;
for(int j=;j<k;j++)
ans[j]=a[j];
}
}
void dfs(int step)
{
if(step==k)
{
dp();
return;
}
for(int i=a[step-]+;i<=a[step-]*n+;i++)
{
a[step]=i;
dfs(step+);
}
}
int main()
{
scanf("%d%d",&n,&k);
maxn=;
dfs();
for(int i=;i<k;i++) printf("%d ",ans[i]);
printf("\nMAX=%d",maxn);
return ;
}

详细题解戳这里

05-11 14:06