CF1498C Planar Reflections

本文主要是介绍CF1498C Planar Reflections，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
~~明明没那么难，也不知道为什么做了这么长时间，吐了~~

题目大意：
如上图所示：一个能量为 $k$ 的粒子，射入有 $n$ 个反射板的空间，粒子每经过一个反射板，会有一个 $k - 1$ 能量的粒子被反射，当然 $k = 1$ 的时候，就不会反射出粒子。问最后可以有多少个粒子，答案对 $1 e 9 + 7$ 取模。

题目分析：这个是不能在多组输入前预处理出来的，因为 $n$ 和 $k$ 都相互牵制。题目给出的范围正好是可以让我们进行 $O (n * k)$ 的 $d p$ 的。用 $d p [k] [n]$ 来表示能量为 $k$ 并且面前有 $n$ 个挡板的粒子个数。首先，面前有 $n$ 个挡板能量为k的粒子个数会有一部分是由 $k + 1$ 能量，面前有 $N - n$ 个面板反射的(因为是反方向，所以要有是 $N - n$ ， $N$ 为总挡板，这个一画图就可以看出来)，另外一部分是由 $k + 1$ 能量，面前大于 $N - n$ 个挡板的粒子反射的，而这部分就是反射能量为 $k$ 并且面前有 $n - 1$ 个挡板的粒子的总粒子。所以就有： $d p [k] [n] = d p [k] [n - 1] + d p [k + 1] [N - n]$ 。
特别的： $d p [K] [N] = 1$ ， $d p [K - 1] [0] = 1$ ，其他初始化都为0， $d p [K] [N] = 1$ 不用多说，初始就射入一个粒子。对于 $d p [K - 1] [0] = 1$ ，因为射入的时候，会在第一个挡板的外部反射出一个粒子，所以 $K - 1$ 能量的粒子就会有一个面前没有挡板，其余情况，当第一个粒子穿过所有挡板后，其他的粒子就会在挡板之间反射，不会再出现像第一个粒子那样反射出面前有0个挡板的情况了。
最终答案就是把所有可能出现的粒子加和。

code：

#include <bits/stdc++.h>using namespace std;
#define fast                      \ios_base::sync_with_stdio(0); \cin.tie(NULL);
typedef long long ll;
const int N = 1010;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;int dp[N][N];
void done(int K, int NN) {dp[K][NN] = 1;dp[K - 1][0] = 1;for (int k = K - 1; k >= 1; k--) {for (int n = 1; n <= NN - 1; n++) {dp[k][n] = dp[k][n - 1] + dp[k + 1][NN - n];dp[k][n] = dp[k][n] % mod;}}
}void solve() {int n, k;scanf("%d%d", &n, &k);for (int i = 0; i <= k; i++) {dp[i][0] = 0;dp[i][n] = 0;}for (int i = 0; i <= n; i++) {dp[k][i] = 0;}done(k, n);int ans = 0;for (int i = 1; i <= k; i++) {for (int j = 0; j <= n; j++) {ans = (ans + dp[i][j]) % mod;}}printf("%d\n", ans % mod);
}int main() {int T;scanf("%d", &T);while (T--) {solve();}return 0;
}