11064: 【原1064】小M爱炒股

题目描述

author: duruofei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1064

Description

小M最近喜欢上了炒股。作为一个爱思考的孩子，小M发现了一条炒股秘诀——"逢低吸纳,越低越买"!

这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低，按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。小M想让你帮他写一个程序，求出最多能买几次股票。

以下面这个表为例, 某几天的股价是:

(Here put the table)

这个例子中, 小M如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):

(Here put the table)

Input Format

第1行: N (\( 1 \leq N \leq 5000 \) ), 表示能买股票的天数。

第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++)

Output Format

只有一行，输出两个整数：

能够买进股票的天数长度达到这个值的股票购买方案数量

在计算方案的数量的时候，如果两个方案的股价序列相同，那么这样的两个方案被认为是相同的（只能算做一个方案）。因此，两个不同的天数序列可能产生同一个股价序列，这样只能计算一次。

Sample Input

12
68 69 54 64 68 64 70 67
78 62 98 87

Sample Output

4 2

FineArtz's solution

/* 小M爱炒股 */
#include <iostream>
#include <cassert>
using namespace std;

class Bignum{
public:
    int len = 1;
    long long data[1005] = {0};

    long long &operator [](int x){
        return data[x];
    }

    void clear(){
        for (int i = 1; i <= len; ++i)
            data[i] = 0;
        len = 1;
    }

    Bignum &operator =(const Bignum &b){
        clear();
        len = b.len;
        for (int i = 1; i <= len; ++i)
            data[i] = b.data[i];
        return *this;
    }
};

Bignum operator +(const Bignum &b1, const Bignum &b2){
    Bignum c;
    c.len = max(b1.len, b2.len);
    for (int i = 1; i <= c.len; ++i){
        c.data[i] = c.data[i] + b1.data[i] + b2.data[i];
        c.data[i + 1] += c.data[i] / 10;
        c.data[i] %= 10;
    }
    ++c.len;
    while (c.data[c.len] != 0){
        c.data[c.len + 1] += c.data[c.len] / 10;
        c.data[c.len] %= 10;
        ++c.len;
    }
    if (c.data[c.len] == 0 && c.len != 1)
        --c.len;
    return c;
}

long long a[5005], len;
int n;
long long t[5005];
Bignum c, cnt[5005];

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        t[i] = 1;
        cnt[i][1] = 1;
    }
    len = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j < i; ++j){
            if (a[j] > a[i]){
                if (t[i] < t[j] + 1){
                    t[i] = t[j] + 1;
                    cnt[i] = cnt[j];
                }
                else if (t[i] == t[j] + 1)
                    cnt[i] = cnt[i] + cnt[j];
            }
        }
        for (int j = 1; j < i; ++j){
            if (a[i] == a[j] && t[i] == t[j])
                cnt[j].clear();
        }
        if (t[i] > len)
            len = t[i];
    }
    for (int i = 1; i <= n; ++i){
        if (t[i] == len)
            c = c + cnt[i];
    }
    cout << len << ' ';
    for (int i = c.len; i >= 1; --i)
        cout << c[i];
    cout << endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 5010;
int n, ans = 1;
int a[MAX_N], num[MAX_N], f[MAX_N], cnt[MAX_N][110], check[MAX_N << 2];

void add(int *x, int *y) {

    int carries = 0, length = 1, z[110] = {0};
    while (length <= x[0] || length <= y[0]) {
        z[length] = x[length] + y[length] + carries;
        carries = z[length] / 10;
        z[length] = z[length] % 10;
        length++;
    }
    z[length] = carries;
    if (!z[length]) length--;
    x[0] = length;
    for (int i = 1; i <= length; ++i) x[i] = z[i];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        f[i] = 1;
    }
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (a[i] < a[j]) f[i] = max(f[i], f[j] + 1);
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
    printf("%d ", ans);

    for (int i = 1; i <= n; ++i) {
        if (f[i] == 1) cnt[i][0] = cnt[i][1] = 1;
        else {
            memset(check, 0, sizeof(check));
            cnt[i][0] = 1;
            for (int j = i - 1; j > 0; --j)
                if (f[j] + 1 == f[i] && !check[a[j]] && a[i] < a[j]) {
                    add(cnt[i], cnt[j]);
                    check[a[j]] = 1;
                }
        }
    }
    memset(check, 0, sizeof(check));
    for (int i = n; i > 0; --i)
        if (f[i] == ans && !check[a[i]]) {
            add(num, cnt[i]);
            check[a[i]] = 1;
        }
    for (int i = num[0]; i >= 1; --i) printf("%d", num[i]);
    return 0;
}