結果

問題 No.209 Longest Mountain Subsequence
コンテスト
ユーザー tottoripaper
提出日時 2015-07-25 21:13:55
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
(最新)
TLE  
(最初)
実行時間 1,701 ms / 2,000 ms
コード長 2,343 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 235 ms
コンパイル使用メモリ 55,008 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-03-30 07:59:00
合計ジャッジ時間 5,959 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <algorithm>

int N;
// [位置][前の位置] = 最大長
int dp[100][100];
int A[100];

int main(){
    int T;
    scanf("%d", &T);

    for(int _=0;_<T;_++){
        scanf("%d", &N);

        for(int i=0;i<N;i++){
            scanf("%d", A+i);
        }
        
        int mx = 0;
    
        for(int i=0;i<N;i++){
            memset(dp, 0, sizeof(dp));
        
            int res = 1;
            for(int j=i-1;j>=0;j--){
                if(A[j] < A[i]){
                    dp[j][i] = 2;
                    res = std::max(res, 2);
                }

                for(int k=j+1;k<i;k++){
                    for(int l=k+1;l<=i;l++){
                        if(A[j] >= A[k] ||
                           A[k] >= A[l] ||
                           A[k] - A[j] >= A[l] - A[k]){
                            continue;
                        }
                        dp[j][k] = std::max(dp[j][k], dp[k][l] + 1);
                        res = std::max(res, dp[j][k]);
                    }
                }
            }

            // printf("%d: %d\n", i, res);
            
            // for(int j=0;j<10;j++){
            //     for(int k=0;k<10;k++){
            //         printf("%3d ", dp[j][k]);
            //     }
            //     puts("");
            // }

            int x = 1;
            for(int j=i+1;j<N;j++){
                if(A[i] > A[j]){
                    dp[j][i] = 2;
                    x = std::max(x, 2);
                }

                for(int k=i;k<j;k++){
                    for(int l=k+1;l<j;l++){
                        if(A[k] <= A[l] ||
                           A[l] <= A[j] ||
                           A[k] - A[l] <= A[l] - A[j]){
                            continue;
                        }

                        dp[j][l] = std::max(dp[j][l], dp[l][k] + 1);
                        x = std::max(x, dp[j][l]);
                    }
                }
            }

            // for(int j=0;j<10;j++){
            //     for(int k=0;k<10;k++){
            //         printf("%3d ", dp[j][k]);
            //     }
            //     puts("");
            // }     
            
            // printf("%d: %d\n", i, x);
            res += x - 1;

            mx = std::max(mx, res);
        }

        printf("%d\n", mx);
    }
}
0