結果

問題 No.127 門松もどき
コンテスト
ユーザー なお
提出日時 2015-01-14 00:33:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 1,353 ms
コンパイル使用メモリ 159,352 KB
実行使用メモリ 180,952 KB
最終ジャッジ日時 2024-06-22 11:18:43
合計ジャッジ時間 7,960 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = (int)1e9+7;

int N,M,W,H;
int A[3333];

int dp[2][3333][3333];

int dfs(int i, int j, int k){
    if(j == k){
        return 1;
    }

    if(dp[i][j][k] >= 0) return dp[i][j][k];
    int res = 0;
    if(i == 0){
        for(int kk = j; kk < k; kk++){
            res = max(res, dfs(0, j, kk));
        }
        for(int jj = j+1; jj <= k; jj++){
            for(int kk = 0; kk <= k-jj; kk++){
                int r = dfs(1, jj, jj+kk);
                if(A[j] < A[jj+kk]){
                    res = max(res, r + 1);
                }
            }
        }
    } else {
        for(int jj = j+1; jj <= k; jj++){
            res = max(res, dfs(1, jj, k));
        }
        for(int jj = j; jj <= k-1; jj++){
            for(int kk = 0; kk <= k-1-jj; kk++){
                int r = dfs(0, jj, jj+kk);
                if(A[jj] > A[k]){
                    res = max(res, r + 1);
                }
            }
        }
    }
    fprintf(stderr, "%d [%d:%d] = %d\n", i, j, k, res);
    return dp[i][j][k] = res;
}

int main(){
    cin >> N;
    REP(i,N){
        cin >> A[i];
    }
    memset(dp, -1, sizeof(dp));

    cout << max(dfs(0, 0, N-1), dfs(1, 0, N-1)) << endl;

}
0