新来的实习生把路由线路搞得一团糟!如图,原本左右端口应当按顺序连接。现在只有切除部分线路,使得任何线路都不相交。希望你写一个程序计算最后剩下多少线路?
关键字:最长上升子序列 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//////////////////////////////////
12510373 | hankcs | 1631 | Accepted | 520K | 469MS | C++ | 876B | 2014-02-10 20:30:50 |
还行。
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 1631 Bridging signals 题解 《挑战程序设计竞赛(第2版)》