洛谷 P1490 买蛋糕 解题报告

P1490 买蛋糕

题目描述

野猫过生日,大家当然会送礼物了(咳咳,没送礼物的同志注意了哈!!),由于不知道送什么好,又考虑到实用性等其他问题,大家决定合伙给野猫买一个生日蛋糕。大家不知道最后要买的蛋糕的准确价格,而只会给蛋糕估价,即要买一个不超过多少钱的蛋糕。众OIer借此发挥:能否用最少的钱币数去凑成估价范围内的所有价值,使得不管蛋糕价值多少,都不用找钱……

现在问题由此引出:对于一个给定的n,能否用最少的不等的正整数去组成n以内(包括n)的所有的正整数呢?如果能,最少需要多少个正整数,用最少个数又有多少不同的组成方法呢?

输入输出格式

输入格式:

只有一行包含一个整数n(1<=n<=1000)。

输出格式:

一行两个数,第一个数是最少需要多少个数,第二个数是用最少个数的组成方案个数。两个答案用空格分隔。


  • 首先明确第一个问题:这个最小的正整数是多少?

也许你可以打表看出来,也许不能,但别急,我们有看似靠谱一点的思维方法

看看样例:6

可行方案:

①\(1\) \(2\) \(3\);

②\(1\) \(2\) \(4\).

我们发现,对于方案①,组成3的时候有两种方法(1+2或3),而方案②只有一种。换而言之,3的利用是有浪费的。而不浪费的方案②还可以组成7。

那么,我们咋让她(每个数)都用好自己呢

很简单,百合就行了

联想一下二进制位下的数

\(1\),\(10\),\(11\),\(100\),\(101\),\(110\),\(111\),\(1000\)...

可不是嘛,这个\(2^i\)的每个数利用率可高了

由此可知,二进制的位数即为这个最小的正整数


  • 想明白第一问以后,应该给出了一个相对的第二问的思维导向。(当然不绝对哈)

当每个数的利用率最大的时候,她们能够凑成的最大整数即为她们的和,这点是毋庸置疑的。

那么,在利用率相对不是那么大的时候呢?

我们注意到,此时已经有了一个限制条件:已有的最小正整数

手动模拟一下,确实是仍然成立的。(其实是不太会证啦)

这时候,我们就把参与量已使用的各数之和凑成的最大整数搞到一起去了

考虑\(dp[k]\)代表凑成时\(k\)的方案数。看看这时候还要压哪些信息进去。

显然,剩下的必要信息还有第\(i\)个数和第\(i\)个数的值\(j\)

\(dp[i][j][k]\)表示已选\(i\)个数,第\(i\)个数为\(j\),前\(i\)个数和为\(k\)(凑成的最大整数位\(k\))的时候的方案数

转移方程 \(dp[i+1][l][k+l]+=dp[i][j][k];\)

其中\(l\)为枚举的下一个填充数

核心代码:

    dp[1][1][1]=1;
for(int i=1;i<ans;i++)
for(int j=i;j<=(1<<(i-1));j++)
for(int k=i*(i-1)/2;k<(1<<i);k++)
for(int l=j+1;l<=k+1;l++)
if(l+k<=n)
dp[i+1][l][k+l]+=dp[i][j][k];
else
dp[i+1][l][n]+=dp[i][j][k];

注意\(j,k,l\)的上下界,都是被已经得到的第一问给约束住了

当然,也没必要跑这么死,比如\(k\)从\(i\)开始反而会快一些。

至于\(if\)和\(else\)的判断,是为了方便求最后结果的一点点小贪心了。


2018.5.2

上一篇:云原生时代, Kubernetes 多集群架构初探


下一篇:VMware扩展Linux根目录磁盘空间(Centos版本)