Created
February 25, 2016 20:07
-
-
Save kurenaif/a5ab6cd749425ed74ea2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <queue> | |
#include <map> | |
#include <list> | |
#include <vector> | |
#include <string> | |
#include <limits> | |
#include <cassert> | |
#include <fstream> | |
#include <cstring> | |
using namespace std; | |
#define FOR(i,a,b) for (int i=(a);i<(b);i++) | |
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) | |
#define REP(i,n) for (int i=0;i<(n);i++) | |
#define RREP(i,n) for (int i=(n)-1;i>=0;i--) | |
#define inf INT_MAX/3 | |
#define INF INT_MAX/3 | |
#define PB push_back | |
#define MP make_pair | |
#define ALL(a) (a).begin(),(a).end() | |
#define SET(a,c) memset(a,c,sizeof a) | |
#define CLR(a) memset(a,0,sizeof a) | |
#define pii pair<int,int> | |
#define pcc pair<char,char> | |
#define pic pair<int,char> | |
#define pci pair<char,int> | |
#define VS vector<string> | |
#define VI vector<int> | |
#define DEBUG(x) cout<<#x<<": "<<x<<endl | |
#define MIN(a,b) (a>b?b:a) | |
#define MAX(a,b) (a>b?a:b) | |
#define pi 2*acos(0.0) | |
#define INFILE() freopen("in0.txt","r",stdin) | |
#define OUTFILE()freopen("out0.txt","w",stdout) | |
#define in scanf | |
#define out printf | |
#define ll long long | |
#define ull unsigned long long | |
#define eps 1e-14 | |
#define FST first | |
#define SEC second | |
int bitcount(long bits) | |
{ | |
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); | |
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); | |
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); | |
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); | |
return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff); | |
} | |
int dpL[3001][3001]; | |
int dpR[3001][3001]; | |
int main(void) { | |
int N; cin >> N; | |
vector<int> A; | |
REP(i, N) { | |
int a; cin >> a; A.push_back(a); | |
} | |
memset(dpL, -1, sizeof(dpL)); | |
memset(dpR, -1, sizeof(dpR)); | |
for (int i = 0; i < N; ++i) { | |
dpL[i][i] = dpR[i][i] = 1; | |
} | |
int res = 0; | |
for (int w = 1; w < N; ++w) { //幅で更新していくといい感じになった | |
for (int l = 0; l < N - w; ++l) { | |
int r = l + w; | |
if (A[l] >= A[r]) dpL[l][r] = dpL[l][r - 1]; | |
else { | |
dpL[l][r] = max(dpL[l][r - 1], dpR[l + 1][r] + 1); | |
} | |
if (A[l] <= A[r]) dpR[l][r] = dpR[l + 1][r]; | |
else { | |
dpR[l][r] = max(dpR[l + 1][r], dpL[l][r - 1] + 1); | |
} | |
res = max(res, dpL[l][r]); | |
res = max(res, dpR[l][r]); | |
} | |
} | |
cout << res << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment