bridging signals(dp(nlogn)).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 43 行

#include <cstdio>
#include <string>
#define NMAX 40100
int p,n;
int seq[NMAX];
int len[NMAX];
int dp[NMAX];

int main()
{
	int i,j;
	scanf("%d", &n);
	while (n --) {
		scanf("%d", &p);
		for (i=1;i<=p;i++) {
			scanf("%d", seq+i);
		}
		dp[0] = dp[1] = 1;
		len[0] = -1;
		len[1] = seq[1];
		int mmax = 1;
		for (i=2;i<=p;i++) {
			dp[i] = 1;
			len[i] = INT_MAX;
			int left = 0, right = mmax;
			while (right >= left) {
				int mid = (left + right) / 2;
				if (seq[i] > len[mid]) {
					left = mid+1;
				}
				else {
					right = mid-1;
				}
			}
			dp[i] = left;
			if (seq[i] < len[ dp[i] ]) {
				len[ dp[i] ] = seq[i];
			}
			mmax = mmax > dp[i] ? mmax : dp[i];
		}//for i
		printf("%d\n", mmax);
	}
}