PKU 1631 Bridging signals
http://poj.org/problem?id=1631
交差しないように橋をかけられる最大の数を答えろというような問題。
dp。
logアルゴリズムが面倒くさかったので平方分割に逃げましたが通ってよかったです。
int p; int b; int arr[40000]; int arr2[40000]; int getv(int t){ int ret=0; rep(i,t/b) ret=max(arr2[i],ret); rep(i,t-t/b*b) ret=max(arr[t/b*b+i],ret); return ret; } void setv(int t,int v){ arr[t]=v; arr2[t/b]=max(arr2[t/b],v); } void solve(){ scanf("%d",&p); b=sqrt(p); memset(arr,0,sizeof(arr)); memset(arr2,0,sizeof(arr2)); int ans=0; rep(i,p){ int t; scanf("%d",&t); int k=getv(t)+1; setv(t,k); ans=max(ans,k); } cout<<ans<<endl; } main(){ int t; scanf("%d",&t); while(t--) solve(); }