立方体塔

 Algorithm
 
  • 描述：

小方有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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010,mod=1e9+7;

int f[N];

int main() {
    int n,m;
    scanf("%d%d",&n,&m);

    int h=1;
    while(h*(h+1)/2<=n+m) h++;
    h--;

    //swap(n,m);

    f[0]=1;
    for(int i=1;i<=h;i++) {
        for(int j=n;j>=i;j--) {
            f[j]=(f[j]+f[j-i])%mod;
        }
    }

    int res=0;
    for(int i=0;i<=n;i++)
        if(h*(h+1)/2-i<=m)
            res=(res+f[i])%mod;

    printf("%d %d\n",h,res);
    return 0;
}

上述代码是滚动数组优化之后f变成一维的情况。f[N]等同于f[N][N],

1
2
3
4
5
6
f[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
6
f[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]等价了。

 Previous

DFS BFS