poj3934Queue

题目链接：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
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include
 9 #include
10 #include
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 }
 
dp动态规划

相关

标签