CF478D-Red-Green Towers

2022-07-26 题解

题目大意：给出r个红色块和g个绿色块，要将它们搭成尽可能高的“塔”。“塔”的第i层有i个块，且要求同一层中块的颜色都一样。问有多少种搭法。

由于每一层之间的块数只差1，因此，只要所需块数的总数小于块的总数，就总是存在放的方案。塔所需要的块的总数总是公差、首项为1的等差数列的和，由此就可以求出塔的最大层数h了。

只要确定了其中一种颜色的放法，另一种颜色的放法也确定了。不妨来确定绿色块的放法。

首先确定绿色块可以放多少个。绿色块放的数目首先不能超过h层塔所需的总块数，也不能超过它本身的数目。另外，应该保证绿色块+红色块的数目不少于h层塔所需的总块数。故绿色块可以放的数目 $i$ 满足

i \in [sum-r,min(g,sum)]

其中r为红色块总数，sum为h层塔所需的总块数，g为绿色块总数。

知道了绿色块可以放多少个之后，只要对于每个i能取的方案数求和就行了。每个i能取的方案数相当于容量为i，物品重量为0,1,2,3,…,i，价值均为1的01背包，（专有名词：01背包求方案数）

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[200005];
signed main()
{
    int r, g, mod = 1e9 + 7;
    scanf("%lld%lld", &r, &g);
    if (r < g)
        swap(r, g);
    int h = (-1 + sqrt(1 + 8 * (r + g))) / 2;
    int sum = h * (h + 1) / 2;

    dp[0] = 1;
    for (int i = 1; i <= h; i++)
    {
        for (int j = r; j; j--)
        {
            if (j >= i)
                dp[j] = (dp[j - i] + dp[j]) % mod;
        }
    }
    int res = 0, n = min(r, sum);
    for (int i = max(0ll, sum - g); i <= n; i++)
        res = (res + dp[i]) % mod;
    printf("%lld\n", res);
    return 0;
}