Buy the Ticket HDU 1133 递推+大数

时间:2023-03-09 04:39:02
Buy the Ticket  HDU 1133  递推+大数

题目连接:

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 */