题目连接:
http://acm.hdu.edu.cn/showproblem.php?pid=1133
题目大意:
有m+n个人去买电影票,每张电影票50元, m个人是只有50元一张的, n个人是只有100元一张的, 电影院自己本身是没有零钱的。 那么要收到100元的钱必须找人家50, 那么再次之前就必须
收到一个50元的, 问你有多少种不同的排列方式。 (注意: 这里每个人都看成了不同的元素)
题目分析:
我们要是能找人家钱首先必须要有 m >= n
我们dp[m][n] 再加一个人 只能又 dp[m-1][n] 和 dp[m][n-1] 转化而来
假设m-1 > n 前面的所有状态都合法
那么 再加入一个带50元人时, 此人的合法的安插位置应该有 m 个, 我们先把这第m个50元的人放在最后, 是 1 种绝对是合法的,因为dp[m-1][n]是合法的放在最后是不影响结果的
我们放在最后这个人可以和前门的 (m-1)个人中的任意一个互换位置, 形成 (m-1) 种情况 加上之前的 1种 总共是 m 种, 同理我们可以推出 n的 情况
递推公式:
dp[m][n] = dp[m-1][n]*m + dp[m][n-1]*n
因为此题的数据范围是100 所以需要用到大数来写
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
const long long maxn =;
const long long INF = 0xfffffff; int dp[maxn][maxn][maxn*];
void Slove()
{
dp[][][] = ;
for(int i=; i<maxn; i++)
{
for(int j=; j<=i; j++)
{
for(int k=; k<*maxn; k++)
{
dp[i][j][k] += dp[i-][j][k]*i + dp[i][j-][k]*j;
dp[i][j][k+] += dp[i][j][k]/;
dp[i][j][k] %= ;
}
}
}
} void Putt(int m,int n)
{
int i;
for(i=*maxn-; i >=; i--)
{
if(dp[m][n][i] != )
break;
}
for(; i >=; i--)
printf("%d", dp[m][n][i]);
printf("%d\n",dp[m][n][]);
} int main()
{
Slove();
int m, n, cas = ;
while(cin >> m >> n, m+n)
{
cout << "Test #" <<cas++ <<":" << endl;
Putt(m,n);
}
return ;
} /* dp[m][n] = dp[m-1][n]*m + dp[m][n-1]*n */