描述
给定一个信封,最多只允许粘贴N张邮票,计算在给定M(N+M<=10)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大max ,使得1~max之间的每一个邮资值都能得到。
例如,N=3,M=2,如果面值分别为1分、4分,则在l分~6分之间的每一个邮资值都能得到(当然还有8分、9分和12分):如果面值分别为1分、3分,则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3,M=2时,7分就是可以得到连续的邮资最大值,所以MAX=7,面值分别为l分、3分。
样例输入:共一行,两个整数,分表为N与M的值。
格式
输入格式
一行,分别为N,M。
输出格式
两行。
第一行为m种邮票的面值,按升序排列,各数之间用一个空格隔开。
第二行为最大值。
如果有多解,输出字典序最大的一个。
限制
各个测试点1s
来源
NOIP1999
(转自https://vijos.org/p/1179)
这道题首先看数据范围就大概能够猜出是搜索,可是,出现了以下问题
1)搜索的范围,不可能从1搜到1000
2)如何求MAX
先来思考问题二,首先回顾一下求出面值为i所需最少的邮票怎么求,用动规对不对?
f[i] = min(f[i - 面额] + 1, f[i]),这样求的对不对?
那从1一直往下做,求到某个f[i] > n,说明什么?i这个面值不能用要超过n张的邮票
凑出来,故MAX = i - 1
问题二解决了,然后来解决问题一,首先上限,很容易想到,当前的MAX + 1,为什么
不能是MAX + 2,或者更多,因为MAX + 1就凑不出来了。然后来思考下限,前一个面额 + 1?
如果比它少会发生什么?MAX貌似不会改变。所以得到了这个范围[前一个面额 + 1, 当前MAX]
接下来附上代码
Code
/**
* vijos.org
* Problem#1179
* Accepted
* Time:107ms
* Memory:568k
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int buf[];
int ans[];
int f[];
int n ,k;
int maxv = ;
int cale(int count){
if(!count) return ;
memset(f, 0x7f, sizeof(f));
f[] = ;
int i = ;
do{
for(int j = ;j <= count && buf[j] <= i;j++)
f[i] = min(f[i - buf[j]] + , f[i]);
}while(f[i++] <= n);
return i - ;
}
void search(int sec){
if(sec >= k){
int c = cale(k);
if(c <= maxv) return;
for(int i = ;i <= k; i++)
ans[i] = buf[i];
maxv = c;
return;
}else{
int temp = cale(sec);
for(int i = temp + ;i > buf[sec]; i--){
buf[sec + ] = i;
search(sec + );
}
}
}
int main(){
cin >> n >> k;
search();
for(int i = ;i <= k;i++)
cout<<ans[i]<<" ";
cout<<endl;
cout<<"MAX="<<maxv;
return ;
}
noip 邮票面值设计 - 搜索 - 动态规划的更多相关文章
-
P1021 邮票面值设计——搜索+完全背包
P1021 邮票面值设计 题目意思是你最多用n张邮票,你可以自己设定k种邮票的面值,每种邮票数量无穷,你最多能用这k种邮票在不超过n张的情况下,组合成的价值要求是从1开始连续的, 求最大能连续到多少: ...
-
NOIP1999邮票面值设计[搜索|DP]
题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤40)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX之间的每一个邮资值都能得到 ...
-
邮票面值设计 (动态规划+DFS)
题意:https://ac.nowcoder.com/acm/problem/16813 思路: 深度搜索:每一层枚举一个面值,然后通过dp进行检查,并通过已知面值得到最多n张得到的最大表示数. 其实 ...
-
深搜+DP剪枝 codevs 1047 邮票面值设计
codevs 1047 邮票面值设计 1999年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...
-
P1021 邮票面值设计
P1021 邮票面值设计 题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1-MAX ...
-
[NOIP1999提高] CODEVS 1047 邮票面值设计(dfs+dp)
dfs出邮票的各种面值,然后dp求解. ------------------------------------------------------------------------------- ...
-
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 ...
随机推荐
-
jQuery.ajax(url,[settings])
概述 通过 HTTP 请求加载远程数据. jQuery 底层 AJAX 实现.简单易用的高层实现见 $.get, $.post 等.$.ajax() 返回其创建的 XMLHttpRequest 对象. ...
-
BZOJ 2286 消耗战 (虚树+树形DP)
给出一个n节点的无向树,每条边都有一个边权,给出m个询问,每个询问询问ki个点,问切掉一些边后使得这些顶点无法与顶点1连接.最少的边权和是多少.(n<=250000,sigma(ki)<= ...
- 很重要的vue的生命周期
-
MySQL5.6忘记root密码(win平台)
1.首先net stop mysql服务,并且切换到任务管理器,有与mysql有关的,最好关闭进程. 2.运行CMD命令切换到MySql安装bin目录,下面是我的mysql安装目录 cd C:\Pr ...
-
Sql导出数据报错-->;SQL Server 阻止了对组件 &#39;Ad Hoc Distributed Queries&#39; 的 STATEMENT&#39;OpenRowset/OpenDatasource&#39; 的访问
SQL Server 阻止了对组件 'Ad Hoc Distributed Queries' 的 STATEMENT'OpenRowset/OpenDatasource' 的访问,因为此组件已作为此服 ...
-
JavaScript - call(this)
为什么使用call(this), 而不是直接使用(function(){})(); "use strict" function Foo() { (function() { cons ...
-
PXE批量部署linux操作系统
前言 在实际生产环境中,有时候我们会碰到为几十上百甚至上千台服务器安装Linux操作系统的需求,如果我们还是常规的去使用移动介质逐台安装,显然是一件低效又令人抓狂的事情,那要安装到何年何月啊?这对于我 ...
-
python 错误AttributeError: &#39;module&#39; object has no attribute &#39;AF_INET&#39;
写了一个简单的python socket的程序.运行时,报错如下 原因:文件的命名与Python的function的命名冲突 修改名称后,发现还是无法运行,检查目录下面是否有 这样子的一个文件,删除即 ...
-
probabilistic robotics_Kalman filter(一)
码农生活告一段落,继续.... 多元正态分布 协方差矩阵,为正定对称矩阵.det表示行列式 协方差反应随机样本变量各分量之间的相关性. 当变量的假设模型不一致时,不适合用高斯滤波. 叠加高斯噪声的线性 ...
-
Hive学习笔记记录
典型数据来源: 文件管理服务: FTP文件服务:采用c/s模式,用户可以通过不同的客户端实现文件的上传与下载. NFS文件服务:借助于TCP/IP协议实现网络文件共享 Samba文件服务:是一种在局域 ...