Skip to content

11296: 【原1296】buylow

题目

题目描述

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

Description

大一鸣回山东滑雪去啦!他找到了一座很有趣的山,这座山横着看起来由好几段连续同高度的平台组成。现在他想知道他最远能滑过几个平台。 显然他只能从高处往低处划同时他喜欢从山左往山右划。

Input Format

第一行:N(1<=N<=5000) 表示这座山由N个平台组成

第二行及以下:N个正整数,分别表示N个平台的高度。

Output Format

只有一行,两个正整数: 能够滑行的最长距离和达到最长距离滑行的方案数(在计算方案时,只要平台高度序列相同就算同一方案,不考虑平台选择的不同)

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];
inline int read() {
    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() {
    n = read();
    for (register int i = 0; i < n; ++i)
        a[i] = read();
    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 read(){
    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(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
}
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;
}