どうにか通せた。
https://atcoder.jp/contests/abc262/tasks/abc262_g
問題
空の数列X、空のスタックSとN要素の数列Aが与えられる。
Aの要素aに対し、順に以下の処理を行う。
- aを捨てる
- aをSにpushする
また、途中任意のタイミングでSの内容をpopしてXに追加できる。
Xを単調増加列になるようにするとき、最大要素数を求めよ。
解法
f(L,R,min,max) := Aの部分列A[L...(R-1)]に対し、問題の手順で構成できるXのうち、最小値がmin以上、最大値がmax以下である最大要素数
とする。求めたいのは、f(0,N,min(A),max(A))である。
f(L,R,min,max)に対し以下の状態分岐が考えられる。
- 先頭要素を捨て、f(L+1,R,min,max)を考える
- 部分列を2つに分割し、f(L,M,min,mid)+f(M,R,mid,max)の最大値を考える。M,midは総当たりする。
- 先頭要素を最初にXに入れ、1+f(L+1,R,A[L],max)を考える。
- 先頭要素を最後にXに入れ、1+f(L+1,R,min,A[L])を考える。
fは状態としてO(N^4)、状態遷移はO(N^2)通りあり、愚直に行うとO(N^6)かかりちょっと時間が短い。
ただ、A[L..(R-1)]に対し、有効なmin,maxの値はA[L...(R-1)]に含まれるものだけなので、このことを利用して状態数を減らすとO(N^6)でも何とか通る。
int N,A[55]; int tma[55][55][55]; int tmi[55][55][55]; int memo[55][55][55][55]; int hoge(int L,int R,int mi,int ma) { if(L>=R) return 0; mi=tmi[L][R][mi]; ma=tma[L][R][ma]; if(mi>ma) return 0; if(memo[L][R][mi][ma]>=0) return memo[L][R][mi][ma]; int ret=0; //削除 ret=max(ret,hoge(L+1,R,mi,ma)); //分割 int M,m; for(m=mi;m<=ma;m++) for(M=L+1;M<R;M++) ret=max(ret,hoge(L,M,mi,m)+hoge(M,R,m,ma)); //最初に取るか最後に取る if(A[L]>=mi&&A[L]<=ma) { ret=max(ret,1+hoge(L+1,R,A[L],ma)); ret=max(ret,1+hoge(L+1,R,mi,A[L])); } return memo[L][R][mi][ma]=ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; FOR(x,N) { for(y=x+1;y<=N;y++) { for(i=1;i<=50;i++) { int t=-1; for(k=x;k<y;k++) if(A[k]<=i) t=max(t,A[k]); tma[x][y][i]=t; t=55; for(k=x;k<y;k++) if(A[k]>=i) t=min(t,A[k]); tmi[x][y][i]=t; } } } MINUS(memo); cout<<hoge(0,N,1,50)<<endl; }
まとめ
O(N^6)で通ってびっくり。