HDU 1133(卡特兰数；动态规划)

深碍√TFBOYSˉ_ 2022-09-20 11:18 119阅读 0赞

题意：M+N个人排队买票，票的单价是50￥，每个人只能买一张。 M个人拿50的去买，N个人拿100的去买，然后悲剧的是售票处开始的时候没有钱，所以如果拿100块买票人前面的拿50块买票的人小于或者等于用100块买票的人，这种排队方式就不合法，也就是不能顺利全部都买到票（因为没零钱找了）！

题目分析：

这是一个Catalan数的非常经典的应用，买票问题，首先我们用"0"表示用50块买票的人，用“1”表示用100块买票的人，然而假设m=4,n=3,的一个序列是：0110100显然，它不合法，然后我们把他稍微变化一下：把第一个不合法的“1”后面的所有数0位为1， 1位为0；这样我们得到了另一个序列：0111011，显然他也不是合法的，但是在这里我们关注的不是他合不合法！只是说明每个不合法的都有一个这样的序列跟他一一对应！

所以我们计算公式就是：合法的排列方式=所有排列方式-非法排列方式

我们这里非法排列方式的计算 就是：(![SouthEast][] -  ![SouthEast 1][])\*M!\*N!，然而在这题，因为每个人都是不同的，所以还要乘以 M！\*N！

所以得出最终方程：

F（N）= (![SouthEast][] -  ![SouthEast 1][])\*M!\*N!，

然后再化简一下;

F(N)=(M+N)! \* (M-N+1)/(M+1)

卡特兰数方法：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <climits>
    #include <cstdlib>
    using namespace std;
    
    #define MAXN 300
    
    class Number
    {
    private:
        static int _t[MAXN];
        int* num;
        int len;
        Number(int l, int* t)
        {
            len = l;
            num = new int[len];
            memcpy(num, t, sizeof(int) * len);
        }
    public:
        Number(unsigned int n) 
        { 
            if (n == 0)
            {
                num = new int[2];
                len = 2;
                num[1] = 0;
                num[0] = -1;
                return;
            }
            int t = MAXN;
            while (n > 0)
            {
                _t[--t] = n%10000;
                n /= 10000;
            }
            len = MAXN - t;
            num = new int[len];
            memcpy(num, _t+t, sizeof(int) * len);
        }
        Number() 
        {
            num = new int[1];
            len = 1;
            num[0] = 0;        
        }
        Number operator=(const Number& rhs)
        {
            delete[] num;
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);
            return *this;
        }
        Number(const Number& rhs)
        {
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);        
        }
        ~Number()
        {
            delete[] num;
        }
        friend ostream& operator<< (ostream& os, const Number& rhs)
        {        
            printf("%d", rhs.num[0]);
            for (int i = 1; i < rhs.len; ++i)
            {
                printf("%04d", rhs.num[i]);
            }
            return os;
        }
        Number operator/ (const unsigned int n) const
        {
            int i, l = len, carry = 0;
            for (i = 0; i < l; ++i)
            {
                carry = carry*10000+num[i];
                _t[i] = carry/n;
                carry %= n;
            }
            for (i = 0; i < l; ++i)
                if (_t[i]) break;
            if (i == l) i = l-1;
            return Number(l-i, _t+i);
        }
        Number operator* (const unsigned int n) const
        {
            if (n > INT_MAX/10000) 
            {
                cout << "失败:" << n << endl;
                exit(EXIT_FAILURE);
            }
            int t = MAXN, l = len, carry = 0;
            while (l > 0)
            {
                carry += num[--l] * n;
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (carry)
            {
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            return Number(MAXN-t, _t+t);
        }
        Number operator+ (const Number& rhs)
        {
            int t = MAXN, l1 = len, l2 = rhs.len, carry = 0;
            while (l1 > 0 && l2 > 0)
            {
                carry += rhs.num[--l2] + num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l2 > 0)
            {
                carry += rhs.num[--l2];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l1 > 0)
            {
                carry += num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            if (carry) _t[--t] = carry;
            return Number(MAXN-t, _t+t);
        }
        friend Number operator+ (const unsigned int n, const Number& rhs)
        {
            return Number(n) + rhs;
        }
        friend Number operator* (const unsigned int n, const Number& rhs)
        {
            return rhs.operator* (n);
        }
    };
    int Number::_t[MAXN];
    Number fact[201];
    int main()
    {
        int n, m, i, count = 1;
        fact[0] = fact[1] = 1;
        for (i = 2; i <= 200; ++i)
            fact[i] = fact[i-1]*i;
        while (cin >> m >> n)
        {
            if (m == 0 && n == 0) break;
            cout << "Test #" << count++ << ":" << endl;
            if (n > m) cout << 0 << endl;
            else
            {
                cout << fact[n+m]*(m-n+1)/(m+1) << endl;
            }
        }
        return 0;
    }

动态规划代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <climits>
    #include <cstdlib>
    using namespace std;
    
    #define MAXN 300
    
    class Number
    {
    private:
        static int _t[MAXN];
        int* num;
        int len;
        Number(int l, int* t)
        {
            len = l;
            num = new int[len];
            memcpy(num, t, sizeof(int) * len);
        }
    public:
        Number(unsigned int n) 
        { 
            if (n == 0)
            {
                num = new int[2];
                len = 2;
                num[1] = 0;
                num[0] = -1;
                return;
            }
            int t = MAXN;
            while (n > 0)
            {
                _t[--t] = n%10000;
                n /= 10000;
            }
            len = MAXN - t;
            num = new int[len];
            memcpy(num, _t+t, sizeof(int) * len);
        }
        Number() 
        {
            num = new int[1];
            len = 1;
            num[0] = 0;        
        }
        Number operator=(const Number& rhs)
        {
            delete[] num;
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);
            return *this;
        }
        Number(const Number& rhs)
        {
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);        
        }
        ~Number()
        {
            delete[] num;
        }
        friend ostream& operator<< (ostream& os, const Number& rhs)
        {        
            printf("%d", rhs.num[0]);
            for (int i = 1; i < rhs.len; ++i)
            {
                printf("%04d", rhs.num[i]);
            }
            return os;
        }
        Number operator* (const unsigned int n) const
        {
            if (n > INT_MAX/10000) 
            {
                cout << "失败:" << n << endl;
                exit(EXIT_FAILURE);
            }
            int t = MAXN, l = len, carry = 0;
            while (l > 0)
            {
                carry += num[--l] * n;
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (carry)
            {
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            return Number(MAXN-t, _t+t);
        }
        Number operator+ (const Number& rhs)
        {
            int t = MAXN, l1 = len, l2 = rhs.len, carry = 0;
            while (l1 > 0 && l2 > 0)
            {
                carry += rhs.num[--l2] + num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l2 > 0)
            {
                carry += rhs.num[--l2];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l1 > 0)
            {
                carry += num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            if (carry) _t[--t] = carry;
            return Number(MAXN-t, _t+t);
        }
        friend Number operator+ (const unsigned int n, const Number& rhs)
        {
            return Number(n) + rhs;
        }
        friend Number operator* (const unsigned int n, const Number& rhs)
        {
            return rhs.operator* (n);
        }
    };
    int Number::_t[MAXN];
    
    Number res[109][109];
    
    int main()
    {
        int n, m, i, j, count = 1;
        res[0][0] = 1;
        while (cin >> m >> n)
        {
            if (m == 0 && n == 0) break;
            for (i = 1; i <= m; ++i)
                res[i][0] = res[i-1][0]*(m-i+1);
            for (i = 1; i <= m; ++i)
                for (j = 1; j <= i && j <= n; ++j)
                    res[i][j] = res[i-1][j]*(m-i+1) + res[i][j-1]*(n-j+1);
            cout << "Test #" << count++ << ":" << endl << res[m][n] << endl;
        }
        return 0;
    }

[SouthEast]: https://img-blog.csdn.net/20140114165549921?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYWNtZHJlYW0=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220828/3d080316bf7e432bafc32c9c37cacef6.png