ちょっと迷ったけど、無事解けて良かった。
http://codeforces.com/contest/582/problem/B
問題
N要素の数列Aが与えられる。
この数列をT回繰り返した数列から生成できる、単調増加な部分列の最大要素数を求めよ。
解法
Aの要素は高々N通りなので、最初に座標圧縮しておこう。
まず簡単なDPの要領で、元のAに対し F(x,y) := (Aの部分列のうち、最小要素がx以上、最大要素がy以下である単調増加列の最大長)を求める。
ここからは2種類の解法がある。
1つは、Tは非常に大きいがAの取り得る値は小さいことから、T回Aを繰り返した数列のうち、最小(T-N)回分は同じ値だけを抽出する部分があるはずである。
よって、その同じ値を抽出する値を総当たりしながら、残りN回分のAの繰り返しの最長部分列を求める。
もう一つは自分の解法。
F(x,y)から、ダブリングの要領でAを2,4,8,...,2^i回繰り返した場合の最小要素がx以上、最大要素がy以下である単調増加列の最大長が求められる。
あとは整数累乗テクの要領で、(T & (2^i)) != 0となるiに対する結果を連結させ、最終的にT回繰り返した場合の題意を満たす最大長を求める。
int N,T,M; map<int,int> MM; int A[3030]; int pat[26][101][101]; int res[26][101][101]; void solve() { int i,j,k,l,r,x,y,z; string s; cin>>N>>T; FOR(i,N) cin>>A[i], MM[A[i]]++; M=0; FORR(r,MM) r.second=M++; FOR(i,N) A[i]=MM[A[i]]; FOR(i,N) FOR(x,A[i]+1) for(y=A[i];y>=x;y--) pat[0][x][A[i]] = max(pat[0][x][A[i]],pat[0][x][y]+1); FOR(i,101) FOR(y,M) FOR(x,y) pat[0][x][y] = max(pat[0][x][y],max(pat[0][x+1][y],pat[0][x][y-1])); FOR(i,25) FOR(y,M) FOR(x,y+1) { for(z=x;z<=y;z++) pat[i+1][x][y] = max(pat[i+1][x][y],pat[i][x][z]+pat[i][z][y]); if(T&(1<<i)) { for(z=x;z<=y;z++) res[i+1][x][y] = max(res[i+1][x][y], res[i][x][z]+pat[i][z][y]); } else res[i+1][x][y]=res[i][x][y]; } cout<<res[25][0][M-1]<<endl; }
まとめ
最初前者の方法を思いついたけど、それはそれで実装めんどそうなのでダブリングに行った。
最初平方分割しようと思ったけど、ダブリングで正解だったかな?