USACO 4.3 Buy Low

Essentially a longest decreasing sequence problem that is easy to solve using typical DP approach. Counting the number of such sequences is also not hard, the real problem is that the counts could be too big to fit in 32 or 64 bit integers, so need to use big integers struct.

#include <vector>
#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>
#include <iomanip>

using namespace std;

const int base = 1000000000;
const int base_digits = 9;

struct BigInteger {
    vector<int> a;
    int sign;

    BigInteger() : sign(1) {}
    BigInteger(long long v) {
        *this = v;
    }

    void operator=(const BigInteger &v) {
        sign = v.sign;
        a = v.a;
    }

    void operator=(long long v) {
        sign = 1;
        a.clear();
        if (v < 0) {
            sign = -1, v = -v;
        }
        for (; v > 0; v = v / base) {
            a.push_back(v % base);
        }
    }

    BigInteger operator+(const BigInteger &v) const {
        if (sign != v.sign) return *this - (-v);
        BigInteger res = v;
        for (int i = 0, carry = 0;
             i < (int) max(a.size(), v.a.size()) || carry; ++i) {
            if (i == (int) res.a.size())
                res.a.push_back(0);
            res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
            carry = res.a[i] >= base;
            if (carry) res.a[i] -= base;
        }
        return res;
    }

    BigInteger operator-(const BigInteger &v) const {
        if (sign != v.sign) return *this + (-v);
        if (abs() < v.abs()) return -(v - *this);
        BigInteger res = *this;
        for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
            res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
            carry = res.a[i] < 0;
            if (carry)
                res.a[i] += base;
        }
        res.trim();
        return res;
    }

    void operator+=(const BigInteger &v) {
        *this = *this + v;
    }
    void operator-=(const BigInteger &v) {
        *this = *this - v;
    }

    bool operator<(const BigInteger &v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size() * v.sign;
        for (int i = (int)a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }

    bool operator>(const BigInteger &v) const {
        return v < *this;
    }
    bool operator <= (const BigInteger &v) const { return !(v < *this); }
    bool operator >= (const BigInteger &v) const { return !(*this < v); }
    bool operator == (const BigInteger &v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator != (const BigInteger &v) const { return *this < v || v < *this; }

    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }

    BigInteger operator-() const {
        BigInteger res = *this;
        res.sign = -sign;
        return res;
    }

    BigInteger abs() const {
        BigInteger res = *this;
        res.sign *= res.sign;
        return res;
    }

    friend ostream& operator<<(ostream &stream, const BigInteger &v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int) v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }
};

int N;
vector<int> num, dp;
vector<BigInteger> cnt;

int main() {
    ifstream fin("buylow.in");
    ofstream fout("buylow.out");
    fin >> N;
    num = vector<int>(N, 0);
    dp = vector<int>(N, 0);
    cnt = vector<BigInteger>(N, BigInteger(0));

    for (int i = 0; i < N; ++i) {
        fin >> num[i];
    }
    dp[0] = 1; cnt[0] = 1;
    for (int i = 0; i < N; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (num[j] > num[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }

        for (int j = 0; j < i; ++j) {
            if (num[j] > num[i] && dp[i] == dp[j] + 1) {
                cnt[i] += cnt[j];
            }
        }
        if (cnt[i] == 0) cnt[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (num[j] == num[i] && dp[j] == dp[i]) {
                cnt[i] -= cnt[j]; // remove duplicates.
            }
        }
    }

    int maxLen = *std::minmax_element(dp.begin(), dp.end()).second;
    BigInteger finalCnt = 0;
    for (int i = 0; i < N; ++i) {
        if (maxLen == dp[i]) {
            finalCnt += cnt[i];
        }
    }
    cout << maxLen << " " << finalCnt << endl;
    fout << maxLen << " " << finalCnt << endl;
}