Poj 1631: Bridging signals

poj1631.md

Poj 1631: Bridging signals

題目

分析

嗯，寫過相同題，這題是 LIS 無誤。

以第一筆範測為例，右邊的 ports 變換後為：

5 2 4 1 6 3

這序列的 LIS 即為答案

AC Code

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

int P;
int mapping[40000 + 1];
int data[40000];
int dp[40000];

const int INF = 0x3f3f3f3f;

int solve() {
	for (int i = 0; i < P; i++)
		data[i] = mapping[i + 1];
	
	// LIS
	memset(dp, INF, sizeof(dp));
	for (int i = 0; i < P; i++) {
		*lower_bound(dp, dp + P, data[i]) = data[i];
	}
	
	return lower_bound(dp, dp + P, INF) - dp;
}

int main() {
	int N;
	scanf("%d", &N);
	
	while (N--) {
		scanf("%d", &P);
		for (int i = 1; i <= P; i++) {
			int right;
			scanf("%d", &right);
			mapping[right] = i;
		}
		
		printf("%d\n", solve());
	}
	
	return 0;
}