Gym 102428F - Fabricating Sculptures 题解

优雅的解法。

题解 #

首先我们可以忽略第一层方块。设 $dp_{s,b}$ 表示把 $b$ 个方块放在 $s$ 堆上放法的数量。（有些堆可以是空的)

现在我们考虑一下转移方程，有三种情况：

第一层是满的
最左边的堆是空的
在右边的堆是空的

第一种情况我们可以忽略掉第一层，放置的方法就是 $dp_{s,b-s}$ . 第二，三种情况我们可以忽略掉空的那一堆，所以有 $2\cdot dp_{s-1,b}$ 种放法，但两种情况有重叠，因为有可能左右两堆都是空的，所以要减掉 $dp_{s-2,b}$ 。综上所述，转移方程就是：

$dp_{s,b}=dp_{s,b-s}+2\cdot dp_{s-1,b}-dp_{s-2,b}$

这个可以用记忆化搜索来求。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
 
const int N=5e3+5;
ll dp[N][N];
const int mod=1e9+7;
ll solve(int s,int b){
    if(b==0) return 1;
    if(s<=0) return 0;
    ll& ret=dp[s][b];
    if( ret) return ret;
    ret=0;
    if(s<=b) ret=solve(s,b-s);
    ret=(ret+solve(s-1,b)*2-solve(s-2,b)+mod)%mod;
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int s,b;
    cin>>s>>b;
    cout<<solve(s,b-s);
    return 0;
}