P1021 邮票面值设计

时间:2021-10-01 09:19:54

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表示最大的面值。

输入输出样例

输入样例#1:
3 2
输出样例#1:
1 3
MAX=7
分析:深度优先搜索+动态规划,搜索邮票的不同面值,用动态规划求出这些不同面值的邮票能组合出的最大连续数:
设f[i]表示已知面值的邮票组合出面值为i所需要的最小邮票数,我们把已知的q种不同的邮票面值存在a中,则有状态转移方程:
                                                 f[i]=min{f[i-a[j]]+1}      
然后深度搜索可能的面值组合,然后不断更新最大值即可
 #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 邮票面值设计的更多相关文章

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

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

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

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

  3. 洛谷P1021 邮票面值设计

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

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

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

  5. 洛谷 P1021 邮票面值设计

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

  6. 洛谷——P1021 邮票面值设计

    https://www.luogu.org/problem/show?pid=1021 题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都 ...

  7. 洛谷P1021邮票面值设计

    题目 一道很经典的搜索题,可以锻炼搜索的能力,比如可以用dfs覆盖加dp的方式来寻找+更新答案.而且还可以通过在递归中增加数组的方式来辅助搜索. #include <bits/stdc++.h& ...

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

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

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

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

随机推荐

  1. iis最大工作进程数

    IIS 6.0允许将应用程序池配置成一个Web园(Web Garden).要理解Web园的概念,可以设想这样一种情形:假设有一个IIS 5.0服务器和三个Web网站,每一个Web网站运行着相同的应用程 ...

  2. vs无法调试的时候

    ①选中所有程序可能经过的地方设置断点 ②清空.net frameword对应的缓存,路径"C:\Windows\Microsoft.NET\Framework\v4.0.30319\Temp ...

  3. memcpy、memmove、memset

    void * memcpy(void * dst, const void * src, size_t count) { void *res=dst; while (count--) { *(char* ...

  4. 嵌入式linux加载引导内核和根文件系统的方法

    总体来说,嵌入式Linux内核和根文件的引导与PC机差不多.嵌入式linux内核和根文件系统可以存放在各种可能的存储设备中,一般情况下我 们将内核和根文件系统直接烧入到Flash中(包括NOR和NAN ...

  5. Codeforces Round &num;426 &lpar;Div&period; 2&rpar;【A&period;枚举,B&period;思维,C&comma;二分+数学】

    A. The Useless Toy time limit per test:1 second memory limit per test:256 megabytes input:standard i ...

  6. Android图片setBackgroundResource和setImageResource的区别

    网上对于这2个的区别大都是如下所示: setImageResource與xml中的src的屬性才是相匹配的,而setBackgroundResource是與xml中的background屬性相匹配 的 ...

  7. 【java】&colon;Junit

    创建单元测试文件 点击创建测试文件的目录,比如,我要在control目录下添加一个测试类,点击control文件夹 右键->new->other->junit test case 下 ...

  8. 雅思听听app

    最近本人呢,正在紧张的备战雅思考试,因为英语基础很弱,尤其是听力,所以老师推荐了雅思听听这个app,说是特别好使,用了一个多月的,总体来说感觉还是很nice的,但是还有一些小毛病,不过这小毛病瑕不掩瑜 ...

  9. 重写TreeView,多层级节点下批量显示图片,图片支持缩略图和文件名列表切换,支持调用者动态匹配选中,支持外界拖入图片并添加到对应节点下

    1.先看下整体效果 2.前端代码 <UserControl x:Class="iPIS.UI.Base.Tree.ImageTreeControl" xmlns=" ...

  10. hdu2079 选课时间&lpar;题目已修改&comma;注意读题&rpar; 母函数

    计算数的和的种类,母函数裸题 #include<stdio.h> #include<string.h> ],c2[],a,b; int main(){ int T; while ...