- 描述:
小方有w个白色立方体和b个黑色立方体,现在小方想把它们堆成一个立方体塔。
一座高度为h的立方体塔,最底层有h个立方体,每往上一层,所需立方体减一,直到最高层只需要一个立方体。
为了让这座塔看起来美观,小方希望每一层都只能用一种颜色的立方体。
小方希望把这座塔叠的尽可能高,因此他想知道塔的最大高度是多少,以及这个高度的立方体塔能有几种。
两种立方体塔,当且仅当至少有一层的颜色是不同的,则被认为是不同的。
- 输入:
共一行,包含两个整数w和b。
- 输出:
共一行,包含两个整数h和c,分别表示最高塔的高度以及此高度塔的种类数。
因为种类数可能较多,请将c对$10^9+7$取模后的值输出。
- 数据范围:
$0 \le w,b \le 10^5$
- 样例输入:
1 1
4 6
- 样例输出:
1 2
4 2
- 解题思路:0/1背包问题求方案数
假设用到的白色块总数是a,那么“1到h层有多少种选法使得白色块总数是a”就是最后此高度塔的种类数。1到h层有多少种选法使得白色块总数是a,即选出1 ~ h中的若干数,让这些数的加和是a。a不是确定的,还要枚举一下a。对于每个a都求一个f[a],那么$\sum f[a]$就是答案。
f(i,j)是在考虑前i个物品的情况下,体积是j的方案数,有$f(i,j)=f(i-1,j)+f(i-1,j-v[i])$,做恒等变形得$f(j)=f(j)+f(j-i)$,在这里v[i]就是i,第i个物品的体积就是i。
- 参考代码:
1 | #include<iostream> |
上述代码是滚动数组优化之后f变成一维的情况。f[N]等同于f[N][N],1
2
3
4
5
6f[0]=1;
for(int i=1;i<=h;i++) {
for(int j=n;j>=i;j--) {
f[j]=(f[j]+f[j-i])%mod;
}
}
等同于1
2
3
4
5
6f[0][0]=1;
for(int i=1;i<=h;i++)
for(int j=0;j<=n;j++) {
f[i][j]=f[i-1][j];//不选第i个物品
if(j>=i) f[i][j]+=f[i-1][j-i];//如果体积够的话就可以选第i个物品
}
二维变成一维的过程是对代码做恒等变形的过程,f[i][j]=f[i-1][j]和f[j]=f[j]就完全一样了,可以删掉(f[j]本来就等于f[j])。
if(j>=i)可以写到第二个循环里去,将for(int j=0;j<=n;j++)变成for(int j=i;j<=n;j++),因为j < i时循环压根不会执行。
剩下的就是对f[i][j]+=f[i-1][j-i]的变形,如果j从小到大枚举,那么f[i][j]+=f[i-1][j-i]不会等价于f[j]+=f[j-i]:
i是大于0的,所以j-i一定是小于j的,从小到大枚举j的话会先算f[j-i]再算f[j],先算f[j-i]的时候是在第i层算的,那f[j]+=f[j-i]就等价于f[i][j]+=f[i][j-i],而不等价于f[i][j]+=f[i-1][j-i]。
将j改为从大到小枚举(for(int j=n;j>=i;j–))的话就可以了,此时j-i还是比j小,但变成f[j-i]在f[j]后面算(因为j从大到小枚举),此时f[j-i]用的就不是第i层的f[j-i](因为还没算到),而是上一层——第i-1层的f[j-i](还没被更新),那f[j]+=f[j-i]就和f[i][j]+=f[i-1][j-i]等价了。