给定一个信封,最多只允许粘贴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分。
N和K
每种邮票的面值,连续最大能到的面值数。数据保证答案唯一。
3 2
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 邮票面值设计的更多相关文章
-
NOIP1999邮票面值设计[搜索|DP]
题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤40)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX之间的每一个邮资值都能得到 ...
-
[NOIP1999提高] CODEVS 1047 邮票面值设计(dfs+dp)
dfs出邮票的各种面值,然后dp求解. ------------------------------------------------------------------------------- ...
-
深搜+DP剪枝 codevs 1047 邮票面值设计
codevs 1047 邮票面值设计 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...
-
P1021 邮票面值设计
P1021 邮票面值设计 题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX ...
-
P1021 邮票面值设计——搜索+完全背包
P1021 邮票面值设计 题目意思是你最多用n张邮票,你可以自己设定k种邮票的面值,每种邮票数量无穷,你最多能用这k种邮票在不超过n张的情况下,组合成的价值要求是从1开始连续的, 求最大能连续到多少: ...
-
P1021 邮票面值设计(dfs+背包dp)
P1021 邮票面值设计 题目传送门 题意: 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15N+K≤15)种邮票的情况下 (假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大 ...
-
Java实现 蓝桥杯VIP 算法提高 邮票面值设计
算法提高 邮票面值设计 时间限制:1.0s 内存限制:256.0MB 问题描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤13)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮 ...
-
洛谷P1021邮票面值设计 [noip1999] dp+搜索
正解:dfs+dp 解题报告: 传送门! 第一眼以为小凯的疑惑 ummm说实话没看标签我还真没想到正解:D 本来以为这么多年前的noip应该不会很难:D 看来还是太菜了鸭QAQ 然后听说题解都可以被6 ...
-
CODEVS1047 邮票面值设计
题目描述 Description 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤40)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX之 ...
随机推荐
-
[ASP.NET MVC] 使用CLK.AspNet.Identity提供以角色为基础的访问控制(RBAC)
[ASP.NET MVC] 使用CLK.AspNet.Identity提供以角色为基础的访问控制(RBAC) 程序代码下载 程序代码下载:点此下载 前言 ASP.NET Identity是微软所贡献的 ...
-
理解ASP.NET 5的中间件
今天推荐的这篇文章,讲述了如何实现和使用ASP.NET 5的中间件. 虽然在ASP.NET 5中,微软没有再强调OWIN(Open Web Interface for .NET)及其微软官方的OWIN ...
-
如何将SQL Server 2008库导入2000中
v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VM ...
-
HTML5就是现在:深入了解Polyfills
http://blog.csdn.net/wang16510/article/details/8960312 https://github.com/Modernizr/Modernizr/wiki/H ...
-
elasticsearch中的概念简述
Near Realtime(NRT) Elasticsearch接近实时.从为一个文档建立索引到可被搜索,正常情况下有1秒延迟. Cluster 一个集群有一个唯一的名字,默认是"elast ...
-
对Linux 新手非常有用的20 个命令
你打算从Windows换到Linux上来,还是你刚好换到Linux上来?哎哟!!!我说什么呢,是什么原因你就出现在我的世界里了.从我以往的经验来说,当我刚使用Linux,命令,终端啊什么的,吓了我一跳 ...
-
5.6.3.7 localeCompare() 方法
与操作字符串有关的最后一个方法是localeCompare(),这个方法比较两个字符串,并返回下列值中的一个: 如果字符串在字母表中应该排在字符串参数之前,则返回一个负数(大多数情况下是-1,具体的值 ...
-
面向对象(java菜鸟的课堂笔记)
类:相同的东西放在一起 分为属性和动作: 把一组或多组事物相同的特性的描述==>类 属性和动作被称为成员: //声明类的属性信息 public class **{ String name: ...
-
Nginx 关于进程数 与CPU核心数相等时,进程间切换的代价是最小的-- 绑定CPU核心
在阅读Nginx模块开发与架构模式一书时: "Nginx 上的进程数 与CPU核心数相等时(最好每个worker进程都绑定特定的CPU核心),进程间切换的代价是最小的;" &am ...
-
《构建之法》chapter5,6 读书心得
<构建之法>第五章用体育运动等团队例子引出软件开发团队的形式,用更加生活化.形象化的例子让读者更能理解软件开发团队的形式.软件团队形式多样,适用于不同的人员与需求.团队可能会演变的模式有: ...