NOIP1999 邮票面值设计

时间:2021-09-18 08:37:24
题目描述 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

//非原创
#include <cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
int dp[],a[]={},max_a[];
int max,n,k;
void youpiao()
{
int i=,j;
dp[]=;
while(dp[i]<=n)
{
i++;
dp[i]=;
for(j=;j<k&&i>=a[j];j++)
if(dp[i-a[j]]+<dp[i])
dp[i]=dp[i-a[j]]+;
}
if(i->max)
{
max=i-;
for(j=;j<k;j++)
max_a[j]=a[j];
}
}
void dfs(int step)
{
if(step==k)
{
youpiao();
return;
}
int i;
for(i=a[step-]+;i<=a[step-]*n+;i++)
{
a[step]=i;
dfs(step+);
}
}
int main()
{
int i;
while(scanf("%d%d",&n,&k)!=EOF)
{
max=;
dfs();
for(i=;i<k;i++)
{
if(!i)
printf("%d",max_a[i]);
else
printf(" %d",max_a[i]);
}
printf("\nMAX=%d\n",max);
}
return ;
}

NOIP1999 邮票面值设计的更多相关文章

  1. NOIP1999邮票面值设计&lbrack;搜索&vert;DP&rsqb;

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

  2. &lbrack;NOIP1999提高&rsqb; CODEVS 1047 邮票面值设计&lpar;dfs&plus;dp&rpar;

    dfs出邮票的各种面值,然后dp求解. ------------------------------------------------------------------------------- ...

  3. 深搜&plus;DP剪枝 codevs 1047 邮票面值设计

    codevs 1047 邮票面值设计 1999年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题目描述 Description ...

  4. P1021 邮票面值设计

    P1021 邮票面值设计 题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX ...

  5. P1021 邮票面值设计——搜索&plus;完全背包

    P1021 邮票面值设计 题目意思是你最多用n张邮票,你可以自己设定k种邮票的面值,每种邮票数量无穷,你最多能用这k种邮票在不超过n张的情况下,组合成的价值要求是从1开始连续的, 求最大能连续到多少: ...

  6. P1021 邮票面值设计(dfs&plus;背包dp)

    P1021 邮票面值设计 题目传送门 题意: 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15N+K≤15)种邮票的情况下 (假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大 ...

  7. Java实现 蓝桥杯VIP 算法提高 邮票面值设计

    算法提高 邮票面值设计 时间限制:1.0s 内存限制:256.0MB 问题描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤13)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮 ...

  8. 洛谷P1021邮票面值设计 &lbrack;noip1999&rsqb; dp&plus;搜索

    正解:dfs+dp 解题报告: 传送门! 第一眼以为小凯的疑惑 ummm说实话没看标签我还真没想到正解:D 本来以为这么多年前的noip应该不会很难:D 看来还是太菜了鸭QAQ 然后听说题解都可以被6 ...

  9. CODEVS1047 邮票面值设计

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

随机推荐

  1. &lbrack;ASP&period;NET MVC&rsqb; 使用CLK&period;AspNet&period;Identity提供以角色为基础的访问控制&lpar;RBAC&rpar;

    [ASP.NET MVC] 使用CLK.AspNet.Identity提供以角色为基础的访问控制(RBAC) 程序代码下载 程序代码下载:点此下载 前言 ASP.NET Identity是微软所贡献的 ...

  2. 理解ASP&period;NET 5的中间件

    今天推荐的这篇文章,讲述了如何实现和使用ASP.NET 5的中间件. 虽然在ASP.NET 5中,微软没有再强调OWIN(Open Web Interface for .NET)及其微软官方的OWIN ...

  3. 如何将SQL Server 2008库导入2000中

    v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VM ...

  4. HTML5就是现在:深入了解Polyfills

    http://blog.csdn.net/wang16510/article/details/8960312 https://github.com/Modernizr/Modernizr/wiki/H ...

  5. elasticsearch中的概念简述

    Near Realtime(NRT) Elasticsearch接近实时.从为一个文档建立索引到可被搜索,正常情况下有1秒延迟. Cluster 一个集群有一个唯一的名字,默认是"elast ...

  6. 对Linux 新手非常有用的20 个命令

    你打算从Windows换到Linux上来,还是你刚好换到Linux上来?哎哟!!!我说什么呢,是什么原因你就出现在我的世界里了.从我以往的经验来说,当我刚使用Linux,命令,终端啊什么的,吓了我一跳 ...

  7. 5&period;6&period;3&period;7 localeCompare&lpar;&rpar; 方法

    与操作字符串有关的最后一个方法是localeCompare(),这个方法比较两个字符串,并返回下列值中的一个: 如果字符串在字母表中应该排在字符串参数之前,则返回一个负数(大多数情况下是-1,具体的值 ...

  8. 面向对象(java菜鸟的课堂笔记)

    类:相同的东西放在一起 分为属性和动作: 把一组或多组事物相同的特性的描述==>类   属性和动作被称为成员: //声明类的属性信息 public class **{ String name: ...

  9. Nginx 关于进程数 与CPU核心数相等时,进程间切换的代价是最小的-- 绑定CPU核心

    在阅读Nginx模块开发与架构模式一书时: "Nginx  上的进程数 与CPU核心数相等时(最好每个worker进程都绑定特定的CPU核心),进程间切换的代价是最小的;" &am ...

  10. 《构建之法》chapter5&comma;6 读书心得

    <构建之法>第五章用体育运动等团队例子引出软件开发团队的形式,用更加生活化.形象化的例子让读者更能理解软件开发团队的形式.软件团队形式多样,适用于不同的人员与需求.团队可能会演变的模式有: ...