本文主要是介绍poj 3934 Queue（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
告诉你两个数 n 和 m ，表示有 n 个人，身高分别为 1 - n 问有多少种排列方式，使得有 m 对人可以互相看见自己。
以第三组样例为例： 3 2 的排列方式分别为： { 1 2 3 }, { 3 2 1 },{ 2 3 1 },{ 1 3 2} 这四种排列方式满足要求。
解题思路：
我们设一个二维数组： dp [ i ] [ j ] 表示前 i - 1 个人已经排好，现在排最矮的那个 i ，总共有 j 种排列方式。 所以很明显，dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1] * 2 + dp [ i - 1] [ j - 2 ] * ( i - 2)
初始化为 dp [ 0 ] [ 0 ] = dp [ 1 ] [ 0 ] = 1. 上面那个等式的右边，分别表示 把 第 i 个人放在两端， 那么互相能够看到的人数就是之前的人数 + 1（只会增加一对）；把 第 i 个人放在原先队伍的中间，那么互相能够看到的人数是之前人数 + 2 （第 i 个人左右两端的人都可以看到他）
解题掉坑：
对于这种题目，我总是在想如果队伍排列是 xxx的话，一共有多少对人能够看到，所以一直跳不出这个圈，真是弱到家。躺床上睡觉的时候，想到用三维数组记录，分别表示第 i 个人， 有 m 对人可以互相看到，此时第 i 个人的两边 分别为（两端均比它大，两端均比他小，一端比他大一端比他小，他在边上）。但是对于这个数组，一直推不出递推式。现在感觉还是因为没办法跳出那个思维定势，一直在考虑，当排列为XXXX时，有多少对人可以看到。直到看了一份题解，才豁然开朗。
代码不难，但是超时了一次，把每次计算预处理出来，就过了。应该是题目的数据组数比较多的原因。
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int dp[111][11111];
void init()
{memset(dp,0,sizeof(dp));int i,j;dp[0][0]=dp[1][0]=1;for(i=2; i<=80; i++){for(j=1; j<=10000; j++){if(j==1)dp[i][j]=dp[i-1][j-1]*2;else dp[i][j]=dp[i-1][j-1]*2+dp[i-1][j-2]*(i-2);dp[i][j]%=9937;}}
}
int main()
{int n,m,i,j;init();while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0)break;printf("%d\n",dp[n][m]%9937);}return 0;
}
这篇关于poj 3934 Queue（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
