題目鏈接：http://poj.org/problem?id=3934；
解題思路：我們要求的是n個人m對，所以需要兩個狀態，i和j，表示一共i個人，其中j對排列方式的方法數，我們需要尋找一個狀態由哪些狀態來決定（這是解題的關鍵），我們做一個dp題，第一步就是先要找到他的狀態，第二步就是尋找每個狀態之間的轉移方式，所以我們就需要知道第i，j個狀態是由哪些狀態所決定的，不難知道，i個人的排列方式，就是i-1個人的排列方式再插入一個最矮的人，在不同的位置插入一個人所導致的結果是不同的，如果在他的兩端插入那么每種方式就會各自增加一對可以互相看見的同學，如果在任意的兩人之間插入的話，那么每種方式就會增加i-2種（因為i-1個人之間一共有i-2個位置可以插入），如果推到這里，顯然我們就可以得到狀態轉移方程dp[i][j] = dp[i-1][j-1]*2 + dp[i-1][i-2]*(i-2)；//需要注意的是需要先預處理一下dp[1][0] = 1；
AC代碼：
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<vector>
5 #include<map>
6 #include<queue>
7 #include<set>
8 #include<cmath>
9 #include<list>
10 #include<cstring>
11 #include<string>
12 #define ll long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f
15 #define inff 0x7fffffff
16 using namespace std;
17 const int N = 80 + 10;
18 const int M = 10000 + 10;
19 const int mod = 9937;
20
21 int dp[N][M];
22
23 int main() {
24
25 int n, m;
26 //memset(dp, 0, sizeof(dp));
27 dp[1][0] = 1;
28 for (int i = 1; i <= 80; i++) {
29 for (int j = 1; j <= 10000; j++) {
30 if (j >= 1) dp[i][j] = (dp[i - 1][j - 1] * 2) % mod;
31 if (j >= 2) dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * (i - 2)) % mod;
32 }
33 }
34 while (~scanf("%d %d", &n, &m)) {
35 if (n == 0 && m == 0) break;
36 printf("%d\n", dp[n][m]);
37 }
38
39 return 0;
40 }
永遠熱愛，永遠向著光，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/456159.html
標籤：其他