Bridging signals
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 10196 | Accepted: 5577 |
Description
'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.
Input
On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p < 40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping:On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.
Output
For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.
Sample Input
4 6 4 2 6 3 1 5 10 2 3 4 5 6 7 8 9 10 1 8 8 7 6 5 4 3 2 1 9 5 8 9 2 3 1 7 4 6
Sample Output
3 9 1 4
题意:
给出 T,代表有 T 个 case。后每个 case 首先给出 N(1 ~ 40000),代表有 2 * N 个针头,分成左右两边,后顺序给出 N 个数,代表左边针头编号依次 1 ~ N 连着的就是这个序列右边的针头编号。问最多能找出多少对相互之间不相交的线。
思路:
最长上升子序列。DP 的写法是 O (n ^ 2)的,TLE 无疑。所以要用 O (n log n)的写法,num 维护每个子序列长度对应的最小值。
http://blog.csdn.net/dangwenliang/article/details/5728363
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int num[40005]; int main() { int t; scanf("%d", &t); while (t--) { int n, len = 0; scanf("%d", &n); num[len] = -1; while (n--) { int ans; scanf("%d", &ans); if (ans > num[len]) num[++len] = ans; else *lower_bound(num, num + len, ans) = ans; } printf("%d\n", len); } return 0; }
相关推荐
Pku acm 第1631题 Bridging signals 代码,有详细的注释,动态规划
这是关于这三个问题的详解文档 包括了完整代码 和 详细解释
consensus bridging theory and practice
《Wireless Transceiver Architecture Bridging RF and Digital Communication》
分布式一致性经典论文,教你一行一行写出一个 Raft 实现
Bridging Relational and NoSQL Databases
Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads论文中文翻译
详细介绍了比防火墙更安全的网络隔离技术的基本概念,主要的技术分类及各个分类的代表产品,对隔离技术的认识和研究具有极大帮助。
Optimizing Bus Bridging Services in Response
Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm ...Bridging signals Pku acm 1887 Testing the CATCHER Pku acm 3356 AGTC Pku acm 2192 Zipper Pku acm 1080 Humman Gene ...
This tutorial illustrates the implementation of component bridging according to techniques introduced in the first tutorial, Bridging XPCOM/Bonobo -- techniques. It walks the reader through the ...
Bridging the I/O Performance Gap for Big Data Workloads: A New NVDIMM-based Approach
SCI原文:RelationNet++: Bridging Visual Representations for Object Detect
Application Control Engine Module Routing and Bridging Configuration Guide.pdf
Action-oriented process mining: bridging the gap between insights and actions论文翻译
Model reference adaptive control- bridging the gap between theory and practice 理論與實務並重,很實用的書
ARUBA 桥接 配置 介绍如何配置ARUBA的桥接,实现无线网络的连接。
PEGASUS_Bridging_Polynomial_and_Non-polycrypt.pdf
Bridging Vision and Language from the Video-to-Text Perspective A Comprehensive Review.pdf