POJ 3093 Stock Exchange - (DP)

题目链接：http://poj.org/problem?id=3903

#include <stdio.h> 
#include <vector> 
#include <algorithm>
using namespace std;//POJ 3903 Stock Exchangeint main()
{int N;while (scanf("%d", &N) != EOF){vector<int> v(N), dp(N, 1), h(N, -1); // h(i)=j, j is the max which dp[j]>dp[i], otherwise -1.int _max = 0;for (int i = 0; i < N; i++){scanf("%d", &v[i]);for (int j = i - 1; j >= 0;){if (dp[j] >= dp[i]){if (v[j] < v[i]){dp[i] = dp[j] + 1;j = h[j]; // dp[k] < dp[i] is meaningless}else j--;}else j = h[j];}// maintain h[i]for (int k = i - 1; k >= 0;){if (dp[k] > dp[i]){h[i] = k;break;}else k = h[k];}_max = max(_max, dp[i]);}printf("%d\n", _max);}system("pause");return 0;
}