### 题目描述

author: Xutong Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1296

## Sample Input

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

## Sample Output

``````4 2
``````

## Hint

69 68 67 62 和 69 69 64 62

## yyong119's solution

``````#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define MAX_N 5050
#define MAX_LEN 1000
using namespace std;
struct LONG_INT {
char num[MAX_LEN];
LONG_INT() {
num[0] = '0'; num[1] = '\0';
}
LONG_INT operator+(const LONG_INT& num2) {
LONG_INT ans;
int k = 0, cur, state = 0;
for(int i = 0, j = 0; num[i] || num2.num[j];) {
if (!num[i])
cur = num2.num[j++] - '0' + state;
else if (!num2.num[j])
cur = num[i++] - '0' + state;
else
cur = num[i++] - '0' + num2.num[j++] - '0' + state;
ans.num[k++] = cur % 10 + '0';
state = cur / 10;
}
if(state) ans.num[k++] = '1';
ans.num[k] = '\0';
return ans;
}
void init(int a) {
num[0] = '0' + a;
num[1] = '\0';
}
} cnt[MAX_N], total_cnt;
int n, ans;
int a[MAX_N], f[MAX_N];
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
int main() {
for (register int i = 0; i < n; ++i)
for (register int i = 0; i < n; ++i) {
// calc longest sequence
f[i] = 1;
for (register int j = 0; j < i; ++j)
if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);
ans = max(ans, f[i]);
// calc number of solutions
if (f[i] == 1) {
// set to 1
cnt[i].init(1);
}
for (register int j = 0; j < i; ++j) {
if (f[i] == f[j] && a[i] == a[j]) {
// set to 0
cnt[j].init(0);
}
if (f[i] == f[j] + 1 && a[i] < a[j])
// set to sum of 2 number
cnt[i] = cnt[i] + cnt[j];
}
}
printf("%d ", ans);
for (register int i = 0; i < n; ++i)
if (f[i] == ans)
total_cnt = total_cnt + cnt[i];
for (register int i = strlen(total_cnt.num) - 1; i >= 0; --i)
printf("%c", total_cnt.num[i]);
return 0;
}
``````

## zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1296.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef unsigned long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct Simple_Bigint{
int num[105];
Simple_Bigint(){
memset(num, 0, sizeof(num));
num[0] = 1, num[1] = 0;
}
Simple_Bigint& operator += (const Simple_Bigint& b){
int ws = max(num[0], b.num[0]), x = 0;
for (int i = 1; i <= ws; ++i)   {
x = x + num[i] + b.num[i];
num[i] = x % 10;
x /= 10;
}
num[0] = ws;
if (x != 0) num[++num[0]] = x;
return *this;
}
Simple_Bigint& operator= (int x){
memset(num, 0, sizeof(num));
num[0] = 0;
while (x > 0)
num[++num[0]] = x % 10, x /= 10;
return *this;
}
Simple_Bigint& operator= (const Simple_Bigint& b){
memset(num, 0, sizeof(num));
num[0] = b.num[0];
for (int i = 1; i <= num[0]; ++i)
num[i] = b.num[i];
return *this;
}
bool operator! (){
return num[0] == 1 && num[1] == 0;
}
void output(){
for (int i = num[0]; i >= 1; --i)
putchar(num[i] + '0');
}
};
int n, a[5005];
int f[5005] = {0};
Simple_Bigint d[5005];
void init(){
for (int i = 1; i <= n; ++i)
}
void solve(){
f[1] = 1, d[1] = 1;
int ans = 1;
Simple_Bigint ans1;
ans1 = 0;
for (int i = 2; i <= n; ++i){
f[i] = 1;
for (int j = i - 1; j >= 1; --j){
if(a[j] > a[i]) {
if(f[j] + 1 == f[i]) d[i] += d[j];
else if(f[i] < f[j] + 1) f[i] = f[j] + 1, d[i] = d[j];
}
}
for (int j = 1; j < i; ++j)
if (a[i] == a[j] && f[i] == f[j])
d[j] = 0;
if(!d[i]) d[i] = 1;
ans = max(ans, f[i]);
}
for (int i = 1; i <= n; ++i)
if(f[i] == ans) ans1 += d[i];
printf("%d ", ans);
ans1.output();
printf("\n");
}
int main(){
init();
solve();
return 0;
}
``````