JOI春合宿2007: Building

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day2_21.pdf

DPの練習。最長増加部分列問題そのまま。 O(n²)解法で解いた。後でO(nlogn)解法も理解しておきたい。

#include <cstdio>
#include <algorithm>

using namespace std;

int n,b[1000],dp[1000];

int main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&b[i]);
  }
  int ans=0;

  for(int i=0;i<n;i++){
    dp[i]=1;
    for(int j=0;j<i;j++){
      if(b[i]>b[j]){
        dp[i]=max(dp[i],dp[j]+1);
      }
    }
    ans=max(ans,dp[i]);
  }

  printf("%d\n",ans);

  return 0;
}