結果

問題 No.209 Longest Mountain Subsequence
ユーザー tottoripapertottoripaper
提出日時 2015-07-25 21:13:55
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,343 bytes
コンパイル時間 1,653 ms
コンパイル使用メモリ 41,396 KB
実行使用メモリ 8,752 KB
最終ジャッジ日時 2023-09-22 23:10:22
合計ジャッジ時間 6,785 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 837 ms
8,752 KB
testcase_01 AC 680 ms
4,376 KB
testcase_02 AC 598 ms
4,376 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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