なんか本番やたら苦労してるな。
http://codeforces.com/contest/1381/problem/B
問題
1~2NのPermutationがX与えられる。
このPermutationを2つの長さNの配列A,Bに分割したとする。
A,Bをマージソートの要領でマージしたとき、入力列に一致するような、A,Bの分割はあるか判定せよ。
解法
X[i...j]が降順にならんているとき、この部分はA,B同じ側に入らなければならない。
Xはこのような塊がいくつかあると考えると、それをちょうど合計Nずつになるように振り分ける問題になる。
あとはbitsetなどでナップサック問題を解けばよい。
int A; int N; int P[404040]; bitset<4040> F,T; void solve() { int i,j,k,l,r,x,y; string s; cin>>A; while(A--) { cin>>N; FOR(i,2*N) cin>>P[i]; vector<int> V; int cur=0; while(cur<2*N) { x=cur+1; while(x<2*N&&P[cur]>P[x]) x++; V.push_back(x-cur); cur=x; } F.reset(); F[0]=1; FORR(c,V) { F|=F<<c; } if(F[N]) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } }
まとめ
この回レート減少幅ひどかったな。