PKU 1887 Testing the CATCHER
http://poj.org/problem?id=1887
ミサイルを受け取るマシンがある。
このマシンは最初のミサイルを受け取ってからそれより高い場所に移動することが出来ない。
このとき、ミサイルをキャッチしなければならない高さが順番に与えられたときに、最大で何個キャッチできるかを求めろというような問題。
たんなる最長減少部分列を求めるという問題。
O(nlogn)が分からないので、O(n^2)でやりましたが通りました。
スペルミスで死にまくりましたけど。
これでPKU600問AC!!
int in[10000]; int dp[10000]; main(){ int n; int te=0; while(cin>>in[0],~in[0]){ memset(dp,0,sizeof(dp)); cout<<"Test #"<<++te<<':'<<endl; n=1; while(cin>>in[n],~in[n])++n; int ans=0; rep(i,n){ int t=1; rep(j,i) if(in[i]<=in[j])t=max(t,dp[j]+1); dp[i]=t; ans=max(ans,t); } cout<<" maximum possible interceptions: "<<ans<<endl; cout<<endl; } }