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 =120;
const long long  INF = 0xfffffff;

int dp[maxn][maxn][maxn*5];
void Slove()
{
    dp[1][0][0] = 1;
    for(int i=1; i<maxn; i++)
    {
        for(int j=0; j<=i; j++)
        {
            for(int k=0; k<5*maxn; k++)
            {
                dp[i][j][k] += dp[i-1][j][k]*i + dp[i][j-1][k]*j;
                dp[i][j][k+1] += dp[i][j][k]/10;
                dp[i][j][k] %= 10;
            }
        }
    }
}

void Putt(int m,int n)
{
    int i;
    for(i=5*maxn-1; i >=0; i--)
    {
        if(dp[m][n][i] != 0)
            break;
    }
    for(; i >=1; i--)
        printf("%d", dp[m][n][i]);
    printf("%d
",dp[m][n][0]);
}

int main()
{
    Slove();
    int m, n, cas = 1;
    while(cin >> m >> n, m+n)
    {
        cout << "Test #" <<cas++ <<":" << endl;
        Putt(m,n);
    }
    return 0;
}

/*

dp[m][n] = dp[m-1][n]*m + dp[m][n-1]*n

*/

Buy the Ticket HDU 1133 递推+大数

相关推荐