HDU 1297（大数+规律）

小灰灰 2022-09-20 12:43 168阅读 0赞

思路如下：

一个长度n的队列可以看成一个n - 1的队列再追加的1个小孩，这个小孩只可能是：

a.男孩，任何n - 1的合法队列追加1个男孩必然是合法的，情况数为f\[n - 1\]；

b.女孩，在前n - 1的以女孩为末尾的队列后追加1位女孩也是合法的，我们可以转化为n - 2的队列中追加2位女孩；

一种情况是在n - 2的合法队列中追加2位女孩，情况数为f\[n - 2\]；

但我们注意到本题的难点，可能前n - 2位以女孩为末尾的不合法队列（即单纯以1位女孩结尾），也可以追加2位女孩成为合法队列，而这种n - 2不合法队列必然是由n - 4合法队列+1男孩+1女孩的结构，即情况数为f\[n - 4\]。

#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[2];
            len = 2;
            num[1] = 0;
            num[0] = -1;        
        }
        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) 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[1009];
    
    int main()
    {
        int n;
        res[1] = 1, res[2] = 2, res[3] = 4, res[4] = 7;
        for (n = 5; n <= 1000; ++n)
            res[n] = res[n-1] + res[n-2] + res[n-4];
        while (cin >> n)
        {
            cout << res[n] << endl;
        }
        return 0;
    }