結果

問題 No.127 門松もどき
ユーザー codershifthcodershifth
提出日時 2015-11-02 09:46:52
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 179 ms / 5,000 ms
コード長 3,149 bytes
コンパイル時間 1,522 ms
コンパイル使用メモリ 164,504 KB
実行使用メモリ 73,856 KB
最終ジャッジ日時 2024-12-23 22:31:14
合計ジャッジ時間 4,403 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()
using namespace std;
class PineDecorationSequenceMock {
public:
//
// 7
// 5
// 8
// 4
// 3 6
// 2 9
// 1
//
// 7,5,8,4,9,1
// 7,6,9
//
// A[i(1)] < A[i(2)] < ... < A[i(n)] A[i(n+1)]
// A[i(1)]
// i(n) < j j A[i1] > A[j]
//
//
// * dpL
// * l
// * [r+1,N-1] ( i(n) <= r r )
//
//
// j j1 < j2 j
// dpL[l][j1-1] j2
// dpL[l][j2-1] j2
//
// [l,r] DP
void solve(void) {
int N;
cin>>N;
vector<int> A(N);
REP(i,N) cin>>A[i];
// l [l,r]
// * r r
// DP
vector<vector<int>> dpL(N,vector<int>(N,0));
// r [l,r]
vector<vector<int>> dpR(N,vector<int>(N,0));
// DP
REP(w,N)
REP(l,N-w)
{
int r = l+w;
if (l == r) // 0
{
dpL[l][r] = dpR[l][r] = 1;
continue;
}
//
dpL[l][r] = max(dpL[l][r], dpL[l][r-1]); // [l,...,r-1],r
dpR[l][r] = max(dpR[l][r], dpR[l+1][r]); // l,[l+1,...,r]
if ( A[l] < A[r] )
dpL[l][r] = max(dpL[l][r], dpR[l+1][r]+1);
if ( A[l] > A[r] )
dpR[l][r] = max(dpR[l][r], dpL[l][r-1]+1);
}
int ret = 0;
REP(l,N)
FOR(r,l,N)
ret = max({ret, dpL[l][r], dpR[l][r]});
cout<<ret<<endl;
}
};
#if 1
int main(int argc, char *argv[])
{
ios::sync_with_stdio(false);
auto obj = new PineDecorationSequenceMock();
obj->solve();
delete obj;
return 0;
}
#endif
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0