2019-2020 ACM-ICPC Latin American Regional Programming Contest F

https://codeforces.com/gym/102428

首先，令 \(dp[i][j]\) 表示 最下层的有 \(i\) 块， 包括最下层总共还有 \(j\) 块的方案数

容易想到状态方程：$dp[i][j] = \sum_{k = 1} ^ i dp[k][j - i] * (i + 1 - k) $

然而是 \(O(n ^ 3)\) 的，会 T

此时改写上式：

$dp[i][j] = \sum_{k = 1} ^ i -k * dp[k][j - i] + \sum_{k = 1} ^ i (i + 1) * dp[k][j - i] $

现在可以用前缀和维护

注意给 \(dp\) 数组赋初值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;        
const int mod = 1e9 + 7;
int c, n;
ll dp[5005][5005];
ll pre[5005][5005], sum[5005][5005];

int main() {
    scanf("%d%d", &c, &n);
    for(int i = 1; i <= n; i++) dp[1][i] = 1, dp[i][i] = 1;
    for(int j = 1; j <= n; j++) { 
        for(int i = 1; i <= c; i++) {
            if(j < i) continue;
            if(dp[i][j]) continue;
            dp[i][j] = (dp[i][j] + 1ll * (i + 1) * pre[j - i][i] % mod) % mod;
            dp[i][j] = (dp[i][j] - sum[j - i][i] + mod) % mod;
        }
        for(int i = 1; i <= c; i++) {
            pre[j][i] = (pre[j][i - 1] + dp[i][j]) % mod;
            sum[j][i] = (sum[j][i - 1] + 1ll * i * dp[i][j]) % mod;
        }
    }
    printf("%lld\n", dp[c][n]);
    system("pause");
    return 0;
}

p.s. 可惜这题在考场上并不会做，按照本场 5 题的水平还不算好。