# 11064: 【原1064】小M爱炒股

### 题目描述

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

## Description

(Here put the table)

(Here put the table)

## 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;
}