itdef

地址 https://www.papamelon.com/problem/328


解答
以6個接口為例
左端 1 2 3 4 5 6端口對應
右端 4 2 6 3 1 5 端口
如圖 左1連接的是右5 如果選擇這條接線
那么左端其他接口就不能連接右端5以前的接口了，否則就會接線交叉。

按照這個規則，其實我們就是求解。
為了接線不交叉的情況下接入更多的接口， 等同于查找左端可以連接右端接口數字的最長上升子序列

于是有了solve1的代碼，但是時間復雜度是O(n^2),n=40000,結果大大超出10^8，肯定TLE了

于是采用單調隊列優化,dp[i]表示當前獲得的長度為i的最長上升子序列的結尾元素。
每次加入元素時檢查dp數組，若dp數組尾端小于元素，元素直接加入dp數組尾端，否則的話則查找dp數組中第一個大于待加入元素的位置，新元素替換進去；最后dp數組的長度
就是最長上升子序列長度；

因為dp數組內的元素單調，所以可以二分查找，整體復雜u度O(n*logn)
代碼見solve2

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;

const int N = 40010;

int A[N];
int dp[N];
int t, n;

void solve1() {

	cin >> t;
	while (t--) {
		memset(A, 0, sizeof A);
		memset(dp, 0, sizeof dp);
		cin >> n;

		for (int i = 1; i <= n; i++) {
			cin >> A[i];
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (A[i] > A[j]) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
	}


	return ;
}



/*
O(n^2) tle  進行優化
O(nlogn)
每次加入元素時檢查棧頂，若棧頂小于元素，直接加入，否則的話則查找棧中第一個大于待加入元素的元素，換掉它；最后棧的容量就是長度；
因為棧內的元素單調，所以可以二分查找，O(logn)O(logn)替換O(n)O(n)達到優化；
*/

int bsearch(int target, int len) {
	int l = 1; int r = len;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (dp[mid]>=target) r = mid;
		else  l = mid + 1;
	}

	return l;
}

void solve2() {
	cin >> t;
	while (t--) {
		memset(A, 0, sizeof A);
		memset(dp, 0, sizeof dp);
		cin >> n;

		for (int i = 1; i <= n; i++) {
			cin >> A[i];
		}
		int idx = 1; dp[idx] = A[idx];
		for (int i = 2; i <= n; i++) {
			if (A[i] > dp[idx]) {
				dp[idx + 1] = A[i]; idx++;
			}
			else {
				int pos = bsearch(A[i],idx);
				dp[pos] = A[i];
			}
		}

		cout << idx << endl;
	}

	return ;
}

int main()
{
	//solve1(); //tle
	solve2();

	return 0;
}

我的視頻題解空間