P1021 邮票面值设计
题目描述
给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值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分。
输入输出格式
输入格式:
2个整数,代表N,K。
输出格式:
2行。第一行若干个数字,表示选择的面值,从小到大排序。
第二行,输出“MAX=S”,S表示最大的面值。
输入输出样例
3 2
1 3
MAX=7
#include<cstdio>
#include<algorithm>
using namespace std;
int f[],a[],ans[];
int maxn,n,k;
void dp()
{
int i=;
f[] = ;
while (f[i]<=n)
{
i++;
f[i] = 1e8;
for (int j=; j<k&&i>=a[j]; ++j)
f[i] = min(f[i],f[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);
a[] = ;
dfs();
for (int i=; i<k; ++i)
printf("%d ",ans[i]);
printf("\nMAX=%d\n",maxn);
return ;
}
P1021 邮票面值设计的更多相关文章
-
P1021 邮票面值设计——搜索+完全背包
P1021 邮票面值设计 题目意思是你最多用n张邮票,你可以自己设定k种邮票的面值,每种邮票数量无穷,你最多能用这k种邮票在不超过n张的情况下,组合成的价值要求是从1开始连续的, 求最大能连续到多少: ...
-
P1021 邮票面值设计(dfs+背包dp)
P1021 邮票面值设计 题目传送门 题意: 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15N+K≤15)种邮票的情况下 (假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大 ...
-
洛谷P1021 邮票面值设计
题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX之间的每一个邮资值都能得到 ...
-
洛谷P1021邮票面值设计 [noip1999] dp+搜索
正解:dfs+dp 解题报告: 传送门! 第一眼以为小凯的疑惑 ummm说实话没看标签我还真没想到正解:D 本来以为这么多年前的noip应该不会很难:D 看来还是太菜了鸭QAQ 然后听说题解都可以被6 ...
-
洛谷 P1021 邮票面值设计
题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX之间的每一个邮资值都能得到 ...
-
洛谷——P1021 邮票面值设计
https://www.luogu.org/problem/show?pid=1021 题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都 ...
-
洛谷P1021邮票面值设计
题目 一道很经典的搜索题,可以锻炼搜索的能力,比如可以用dfs覆盖加dp的方式来寻找+更新答案.而且还可以通过在递归中增加数组的方式来辅助搜索. #include <bits/stdc++.h& ...
-
深搜+DP剪枝 codevs 1047 邮票面值设计
codevs 1047 邮票面值设计 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...
-
[NOIP1999提高] CODEVS 1047 邮票面值设计(dfs+dp)
dfs出邮票的各种面值,然后dp求解. ------------------------------------------------------------------------------- ...
随机推荐
-
iis最大工作进程数
IIS 6.0允许将应用程序池配置成一个Web园(Web Garden).要理解Web园的概念,可以设想这样一种情形:假设有一个IIS 5.0服务器和三个Web网站,每一个Web网站运行着相同的应用程 ...
-
vs无法调试的时候
①选中所有程序可能经过的地方设置断点 ②清空.net frameword对应的缓存,路径"C:\Windows\Microsoft.NET\Framework\v4.0.30319\Temp ...
-
memcpy、memmove、memset
void * memcpy(void * dst, const void * src, size_t count) { void *res=dst; while (count--) { *(char* ...
-
嵌入式linux加载引导内核和根文件系统的方法
总体来说,嵌入式Linux内核和根文件的引导与PC机差不多.嵌入式linux内核和根文件系统可以存放在各种可能的存储设备中,一般情况下我 们将内核和根文件系统直接烧入到Flash中(包括NOR和NAN ...
-
Codeforces Round #426 (Div. 2)【A.枚举,B.思维,C,二分+数学】
A. The Useless Toy time limit per test:1 second memory limit per test:256 megabytes input:standard i ...
-
Android图片setBackgroundResource和setImageResource的区别
网上对于这2个的区别大都是如下所示: setImageResource與xml中的src的屬性才是相匹配的,而setBackgroundResource是與xml中的background屬性相匹配 的 ...
-
【java】:Junit
创建单元测试文件 点击创建测试文件的目录,比如,我要在control目录下添加一个测试类,点击control文件夹 右键->new->other->junit test case 下 ...
-
雅思听听app
最近本人呢,正在紧张的备战雅思考试,因为英语基础很弱,尤其是听力,所以老师推荐了雅思听听这个app,说是特别好使,用了一个多月的,总体来说感觉还是很nice的,但是还有一些小毛病,不过这小毛病瑕不掩瑜 ...
-
重写TreeView,多层级节点下批量显示图片,图片支持缩略图和文件名列表切换,支持调用者动态匹配选中,支持外界拖入图片并添加到对应节点下
1.先看下整体效果 2.前端代码 <UserControl x:Class="iPIS.UI.Base.Tree.ImageTreeControl" xmlns=" ...
-
hdu2079 选课时间(题目已修改,注意读题) 母函数
计算数的和的种类,母函数裸题 #include<stdio.h> #include<string.h> ],c2[],a,b; int main(){ int T; while ...