洛谷 P1490 买蛋糕
2024-10-01 09:47:05
题目描述
野猫过生日,大家当然会送礼物了(咳咳,没送礼物的同志注意了哈!!),由于不知道送什么好,又考虑到实用性等其他问题,大家决定合伙给野猫买一个生日蛋糕。大家不知道最后要买的蛋糕的准确价格,而只会给蛋糕估价,即要买一个不超过多少钱的蛋糕。众OIer借此发挥:能否用最少的钱币数去凑成估价范围内的所有价值,使得不管蛋糕价值多少,都不用找钱……
现在问题由此引出:对于一个给定的n,能否用最少的不等的正整数去组成n以内(包括n)的所有的正整数呢?如果能,最少需要多少个正整数,用最少个数又有多少不同的组成方法呢?
输入输出格式
输入格式:
只有一行包含一个整数n(1<=n<=1000)。
输出格式:
一行两个数,第一个数是最少需要多少个数,第二个数是用最少个数的组成方案个数。两个答案用空格分隔。
输入输出样例
输入样例#1:
6
输出样例#1:
3 2
说明
各个测试点2s
最少用三个数,有两种方法,分别是:1,2,3和1,2,4。
对于1,2,3有1,2,3,1+3,2+3,1+2+3;
对于1,2,4有1,2,1+2,4,1+4,2+4。
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=;
int n,ans,tot;
int f[][maxn][maxn];
int main(){
cin>>n;
ans=(int)log2(n)+;
f[][][]=;
for(int i=;i<ans;i++)
for(int j=i;j<=(<<(i-));j++)
for(int k=i;k<=((<<i)-);k++)
if(f[i][j][k])
for(int p=j+;p<=k+;p++){
if(p+k<=n)//如果加起来在范围内
f[i+][p][k+p]+=f[i][j][k];
else//加起来不在范围内
f[i+][p][n]+=f[i][j][k];
}
for(int i=;i<=n;i++)
tot+=f[ans][i][n];
cout<<ans<<" "<<tot<<endl;
return ;
}
最新文章
- PHP面向对象的魔术方法.png(不间断更新)
- Android版2048
- Daily Scrum 11.3
- 封装自己的ajax函数
- 二模 (9)day1
- hdu 2460 poj 3694 (双联通+LCA)
- poj 1182 并查集高级应用
- awk的接口实现方案1
- HDU 4642 (13.08.25)
- Java框架之Mybatis(一)
- Makefile 使用总结(转)
- Java WebService接口生成和调用 图文详解>;【转】【待调整】
- Visual Studio 2017 Android 调试无法连接到虚拟机
- Spring学习之旅(四)Spring工作原理再探
- java web石家庄铁道大学课程管理系统
- public,protected,private
- javascript中的立即执行函数(function(){…})()
- Intellij IDEA添加项目依赖
- 邪恶力量第一至九季/全集Supernatural迅雷下载
- [underscore源码学习]——`>;>;` 运算符和二分查找