白準2352半導体設計

リンクテキスト
電線の結び目を避けるために、接続されたポートはできるだけ順方向にしなければならない.つまり、1～3番のポートを2～1番のポートに接続すると、ケーブルがねじれ、1～2～2～3番のポートを接続すると、ねじれは発生しません.
すなわち,最長増分部分数列(LIS)の長さを要求するだけでよいが,問題は40000と入力し,既存のdp方式で解くのはやや困難である.
次はタイムアウトが発生したdpコードです.

int lis(int start) {

	if (start == N - 1) return 1;
	if (start < 0) return -1;

	int& res = cache[start];
	if (res != -1) return res;

	res = 1;
	int cnt = 0;
	int next = ary[start]+1, idx = check[next];
	while (next<= maxnum) {

		if (idx < check[next] && ary[idx] < ary[check[next]]) {
			next++; continue;
		}
		idx = check[next++];
		if (idx != -1 && idx > start) {
			res = max(res, lis(idx) + 1);
		}
	}
	
	return res;
}

このdpでタイムアウトが発生したのは,次の順序を検索する過程で配列全体を巡るため,これを改善するためにlow boundを用いたコードを再記述した.
主なアイデアは対応するブログを参照しています.
[最大増分列]LIS(Longest Increating Subsequence)
ソース:https://jason9319.tistory.com/113

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N;
vector<int> ary;
vector<int>lis;


int main(void) {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		ary.push_back(tmp);
	}
	lis.push_back(-1); lis.push_back(ary[0]);

	for (int i = 1; i < N; i++) {
		if (ary[i] > lis.back()) {
			lis.push_back(ary[i]);
		}
		else {
			int idx = lower_bound(lis.begin(), lis.end() - 1, ary[i])- lis.begin();
			lis[idx] = ary[i];
		}
	}


	cout << lis.size() - 1 << endl;
	return 0;
}