alan23273850 的刷題筆記
d898: 10128 - Queue
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=d898
提交：https://zerojudge.tw/Submissions?problemid=d898&account=allllllan123456
問題：請問 $N\in[1,13]$ 個人排在一起，從前面看過去可以看到 P 個人，從後面看過去可以看到 Q 個人之所有可能的方法數？
解法：也是就經典的 DP，但是這題的遞迴設計比較不好想，為了要能確實利用子問題，我們討論每個排列裡面最矮的人出現的位置，這樣才能盡量不改動子問題的 p 和 q 的值，怎麼說呢？如果最矮的人出現在最左邊，那剩下右邊的 n-1 個人必定出現在 dp[n-1][p-1][q] 的方法數裡；如果最矮的人出現在最右邊，那剩下左邊的 n-1 個人必定出現在 dp[n-1][p][q-1] 的方法數裡；如果最矮的人出現在非端點的中間區域，那麼把這個人抽掉的剩餘人等必定出現在 dp[n-1][p][q] 的方法數裡，而這個所謂非端點的中間區域又有 n-2 種可能，於是整體的遞迴式看起來便是 dp[n][p][q] = (n-2) * dp[n-1][p][q] + dp[n-1][p-1][q] + dp[n-1][p][q-1]。
1#include <bits/stdc++.h>
2using namespace std;
3
4long long dp[14][14][14];
5
6long long f(int n, int p, int q) {
7 if (p<1 || q<1 || p+q>n+1) return 0;
8 if (n == 1) return 1;
9 if (dp[n][p][q]) return dp[n][p][q];
10 return dp[n][p][q] = (n-2) * f(n-1, p, q) + f(n-1, p-1, q) + f(n-1, p, q-1);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int T; cin >> T;
15 while (T--) {
16 int N, P, R; cin >> N >> P >> R;
17 cout << f(N, P, R) << '\n';
18 }
19 return 0;
20}