POJ 1631 Bridging signals 题解 《挑战程序设计竞赛(第2版)》

POJ 1631 Bridging signals

新来的实习生把路由线路搞得一团糟！如图，原本左右端口应当按顺序连接。现在只有切除部分线路，使得任何线路都不相交。希望你写一个程序计算最后剩下多少线路？

关键字：最长上升子序列 LIS 

《2.3 记录结果再利用的“动态规划” 需稍加思考的题目》

这道题目的做法就是求最长上升子序列 LIS 的长度，具体解说请参考《POJ 1065 Wooden Sticks 题解 《挑战程序设计竞赛(第2版)》》，或者 《挑战程序设计竞赛(第2版)》 第65页的解说，一样的原理。

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

pair<int, int> stick[5000 + 16];
int dp[5000 + 16];				// dp[i] := 长度为i+1的下降子序列中末尾元素的最大值

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> stick[i].first >> stick[i].second;
		}
		sort(stick, stick + n);
		memset(dp, -1, n * sizeof(int));
		for (int j = 0; j < n; ++j)
		{
			for (int i = 0; i < n; ++i)
			{

				if (i == 0 || dp[i - 1] > stick[j].second)
				{
					dp[i] = max(dp[i], stick[j].second);
				}
			}
		}
		cout << lower_bound(dp, dp + n, -1, greater<int>()) - dp << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

还行。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1631 Bridging signals 题解 《挑战程序设计竞赛(第2版)》