Codeforces 1498C Planar Reflections dp

传送门：https://codeforces.com/contest/1498/problem/C

题意

有一个粒子，衰变年龄为k，前面有n堵墙，每穿过一堵墙，都会有一个年龄-1的粒子反向前进。

当年龄为1时不反向，问有多少穿过1或者n的墙的粒子。

思路

因为n和k都是$\leq 2000$，所以可以考虑$O(nk)$的dp。 状态为dp[n][k],表示一个粒子前面还有n堵墙，衰变年龄为k的答案数。

k为1，不需要转移，dp[i][1]=1. n为0，不需要转移，dp[0][i]=1.

因为可以继续向前，和反向前行，所以转移方程为 $dp[i][j]=dp[i-1][j]+dp[n-i][j-1]$

因为i会对转移先产生影响，所以要先循环第一维。

Code

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
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n, k; cin >> n >> k;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));
        for(int i = 0;i <= n; i++) dp[i][1] = 1;
        for(int i = 1;i <= k; i++) dp[0][i] = 1;
        for(int j = 1;j <= k; j++) {
            for(int i = 1;i <= n; i++) {
                dp[i][j] = (dp[i - 1][j] + dp[n - i][j - 1]) % mod;
            }
        }
        cout << dp[n][k] << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/08/codeforces-1498c-planar-reflections/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！