動的計画法
http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day2_21.pdf
まずこれのbuildingを解いてみた
#include<iostream> using namespace std; int n; int a[1000]; int dp[1000]; int main(){ cin >> n; for(int i = 0;i< n;i++){ cin >> a[i]; } int res = 0; for(int i = 0; i < n;i++){ dp[i] = 1; for(int j = 0;j < i;j++){ if(a[j] < a[i]){ dp[i] = max(dp[i],dp[j] + 1); } } res = max(res,dp[i]); } cout << res << endl; return 0; }