難しく考えすぎて遠回り。
http://yukicoder.me/problems/293
問題
N個の竹が一列に並んでおり、それぞれの高さはA[i]である。
竹番号を1~Nとして、その番号の部分列が門松列を成すとは、もしくはのいずれかを成すものを指す。
A[i]に対し門松列の最大長を求めよ。
解法
連続した部分列A[x..(x+l)]において、以下の2値を更新していく。
- A[x...(x+l)]のうち左端であるx=i_1かつA[x]が門松列中最小値となるような門松列の最大長L[x][x+l]
- A[x...(x+l)]のうち右端であるx+l=i_MかつA[x+l]が門松列中最小値となるような門松列の最大長R[x][x+l]
以下の事実より、幅lを一つずつ広げながらDPしていけば良い。
- L[x][x+l]=max(L[x][x+m]) (m < l)
- A[x] < A[x+l]のとき、L[x][x+l]=R[x+1][x+l]+1 で最大値更新
- R[x][x+l]=max(L[x+m][x+l]) (m < l)
- A[x] > A[x+l]のとき、R[x][x+l]=L[x][x+l-1]+1 で最大値更新
int N; int A[10101]; int dp[2][3030][3030]; void solve() { int i,j,k,l,r,x,y; string s; int ma=1; cin>>N; FOR(i,N) cin>>A[i], dp[0][i][i]=dp[1][i][i]=1; for(i=1;i<=N;i++) for(x=0;x+i<N;x++) { dp[1][x][x+i] = max(dp[1][x][x+i],dp[1][x][x+i-1]); dp[0][x][x+i] = max(dp[0][x][x+i],dp[0][x+1][x+i]); if(A[x]<A[x+i]) dp[1][x][x+i] = max(dp[1][x][x+i],dp[0][x+1][x+i]+1); if(A[x]>A[x+i]) dp[0][x][x+i] = max(dp[0][x][x+i],dp[1][x][x+i-1]+1); ma=max(ma,dp[1][x][x+i]); ma=max(ma,dp[0][x][x+i]); } cout<<ma<<endl; }
まとめ
O(N^3)はすぐ思いついて、そこから探索量を減らそうと頑張ってしまったな…。
そのままでもO(N^2*logN)位で解けそうだけど、無駄に頑張りすぎた。