結果

問題 No.209 Longest Mountain Subsequence
ユーザー kakira9618kakira9618
提出日時 2015-05-16 02:14:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 1,999 bytes
コンパイル時間 669 ms
コンパイル使用メモリ 89,708 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-20 09:00:50
合計ジャッジ時間 1,446 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
4,376 KB
testcase_01 AC 23 ms
4,376 KB
testcase_02 AC 21 ms
4,380 KB
testcase_03 AC 63 ms
4,376 KB
testcase_04 AC 63 ms
4,380 KB
testcase_05 AC 7 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <memory>
#include <functional>
 
using namespace std;

int LL[111][111];
int RR[111][111];

int dfsLL(vector<int> &v, int i, int j) {
    if (LL[i][j] >= 0) return LL[i][j];

    int ans = 0;
    for (int k = 0; k < i; k++) {
        if (v[k] < v[i] && v[i] - v[k] < v[j] - v[i]) ans = max(ans, dfsLL(v, k, i) + 1);
    }
    return LL[i][j] = ans;
}

int dfsRR(vector<int> &v, int i, int j) {
    if (RR[i][j] >= 0) return RR[i][j];

    int ans = 0;
    for (int k = j + 1; k < v.size(); k++) {
        if (v[k] < v[j] && abs(v[j] - v[k]) < abs(v[j] - v[i])) ans = max(ans, dfsRR(v, j, k) + 1);
    }
    return RR[i][j] = ans;
}

int main(int argc, char const *argv[]) {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int N;
        cin >> N;
        vector<int> v;
        for (int i = 0; i < N; i++) {
            int temp;
            cin >> temp;
            v.push_back(temp);
        }
        for (int i = 0; i < 111; i++) {
            for (int j = 0; j < 111; j++) {
                LL[i][j] = -1;
                RR[i][j] = -1;
            }
        }
        int ans = -1;
        for (int center = 0; center < N; center++) {
            int lma = 0, rma = 0;
            for (int i = 0; i < center; i++) {
                if (v[i] < v[center]) lma = max(lma, dfsLL(v, i, center) + 1);
            }
            for (int i = center + 1; i < N; i++) {
                if (v[i] < v[center]) rma = max(rma, dfsRR(v, center, i) + 1);
            }
            //cout << "debug : " << center << " : " << lma << " " << rma << endl;
            ans = max(ans, lma + rma + 1);
        }
        cout << ans << endl;

    }
    return 0;
}
0