Luogu P1350车的放置

分析

排列组合题目，但是 dp 做法。

存储当前列的高度 \(h_i\)，这里反着存，更好转移。

定义状态 \(f_{i,k}\) 为在前 \(i\) 列放置 \(k\) 个车的方法数。初始状态 \(f_{i,0} = 1\)。

分析状态转移方程：

• 当前列不放置车时：方法数为 \(f_{i-1,j}\)
• 当前列放置车时：方法数为 \(f_{i,j-1} * (h_i - j + 1)\)

将两种情况结合，状态转移方程就出来了：
\(f_{i,j} = f_{i-1,j} + f_{i,j-1} * (h_i - j + 1)\)

Accepted Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int mod = 1e5 + 3;
int f[N][N], high[N], a, b, c, d, k, n;
int main()
{
	cin >> a >> b >> c >> d >> k;
	n = a + c;
	for (int i = 1; i <= c; i++)high[i] = d;
	for (int i = c + 1; i <= n; i++)high[i] = b + d;
	for (int i = 0; i <= n; i++)f[i][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * (high[i] - j + 1)) % mod;
	cout << f[n][k];
	return 0;
}