[HZNUOJ1524]排队买票(DP)

题目链接：http://acm.hznu.edu.cn/JudgeOnline/problem.php?id=1524

简单分析后可以知道每一个手持两元的小朋友前面，售票员手里至少有一个一元。

假设dp(i, j)表示当有i个1元和j个2元的时候的排队方法（不重复），那么有：

dp(i, j)=∑k[0, j]dp(i-1, k)， (i >= j)

题干讲n个人和k个人内部不同位置也算新的排列方法。那么最后要乘上A(k,k)*A(n,n)

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int maxn = 15;
23 int n, m, k;
24 int dp[maxn][maxn];
25 
26 int main() {
27     // freopen("in", "r", stdin);
28     scanf("%d %d %d", &m, &n, &k);
29     memset(dp, 0, sizeof(dp));
30     int ak = 1, an = 1;
31     for(int i = 1; i <= k; i++) ak *= i;
32     for(int i = 1; i <= n; i++) an *= i;
33     dp[1][0] = 1;
34     dp[1][1] = 1;
35     for(int i = 2; i <= n; i++) {
36         for(int j = 0; j <= i; j++) {
37             for(int k = 0; k <= j; k++) {
38                 dp[i][j] += dp[i-1][k];
39             }
40         }
41     }
42     printf("%d
", dp[n][k]*ak*an);
43     return 0;
44 }