結果

問題 No.209 Longest Mountain Subsequence
ユーザー tottoripaper
提出日時 2015-07-25 21:13:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,343 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 36,992 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 13:52:17
合計ジャッジ時間 9,154 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
main.cpp:15:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:18:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |             scanf("%d", A+i);
      |             ~~~~~^~~~~~~~~~~

ソースコード

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