首页 > ACM题库 > HDU-杭电 > hdu 2583 permutation-动态规划-[解题报告]C++
2014
02-10

hdu 2583 permutation-动态规划-[解题报告]C++

permutation

问题描述 :

Permutation plays a very important role in Combinatorics. For example ,1 2 3 4 5 and 1 3 5 4 2 are both 5-permutations. As everyone’s known, the number of n-permutations is n!. According to their magnitude relatives ,if we insert the sumbols "<" or ">"between every pairs of consecutive numbers of a permutations,we can get the permutations with symbols. For example,1 2 3 4 5 can be changed to 1<2<3<4<5, 1 3 5 4 2 can be changed to 1<3<5>4>2. Now it’s yout task to calculate the number of n-permutations with k"<"symbol. Maybe you don’t like large numbers ,so you should just geve the result mod 2009.

输入:

Input may contai multiple test cases.
Each test case is a line contains two integers n and k .0<n<=100 and 0<=k<=100.
The input will terminated by EOF.

输出:

Input may contai multiple test cases.
Each test case is a line contains two integers n and k .0<n<=100 and 0<=k<=100.
The input will terminated by EOF.

样例输入:

5 2

样例输出:

66

/*the number of n-permutations with k"<"symbol is F[n][k]
  find the turning
  F[i][0]=1,F[i][i-1]=1,i>j,i(n),j(k) 0<i<=100,0<=k<=100
  以1 3 2 5 4为例,如果我们要插入6,如何办,分<和>分析可知
  F[n+1][k] = F[n][k]*(k+1)+F[n][k-1]*(n-k+1)
  F[1][0]=F[2][0]=F[3][0]=F[4][0]=.....=F[n][0]=1;
  F[1][0]=F[2][1]=F[3][2]...............F[n][n-1]=1;
  转移式:
  F[n][k] = F[n-1][k]*(k+1)+F[n-1][k-1]*(n-k)*/

#include<iostream>
using namespace std;

int F[105][105];
int n,k;

void DP()
{
	int i,j;
	for(i=1; i<=100; ++i)
		F[i][0] = F[i][i-1] = 1;
	for(i=1; i<=100; ++i)
	{
		for(j=0; j<i-1; ++j)
		{
			F[i][j] = (F[i-1][j]*(j+1)+F[i-1][j-1]*(i-j)) % 2009;
		}
	}
}
int main()
{
	DP();
	while(cin >> n >> k)
	{
		cout << F[n][k] << endl;
	}
	return 0;
}

解题转自:http://blog.csdn.net/linraise/article/details/17138931