Bridging signals

Bridging signals
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 10926Accepted: 5982

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.


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


Source

Northwestern Europe 2003

思路转载自大神~~~

题目大意:两边都有N个点,给你N个点的连线关系,现在删除一些线,使剩下的线不想交,

求不相交的线最多有多少条。

思路:都知道是最长上升子序列,那么怎么来的呢

比如说现在有6对点,从上到下,左右两边的点是依次递增排序的。如果想让总的不相交的线数

最多,那么从左边第一个点开始,每个点就要尽可能和右边序号最小的点连接,这样以后的点才

能和更多的点连接。但是如果之后两个及两个以上的点所能连接的点比第一个点连接的右边点

序号小,且不相交,则舍弃第一个,选择之后的点,否则选择前一个。

如题目中的图所示:

左1和右4相连接,之后左2和右2相连接,产生相交,右2比右4小,则舍弃左1和右4,

选择左2和右2的连接

之后左3和右6相连接,右6比右2大,不产生相交,则选择左3和右6的连接;

之后左4和右3相连接,产生相交,右3比之前右6小,则舍弃左3和右6的连接,选择左

4和右3的连接

之后左5和右1相连接,与之前两条线都相交,右1比之前的右3小,同时也比右2小,舍

弃前两个连接选择这一个不符合最优情况,所以舍弃;

之后左6和右5连接,右5比右2大,不产生相交,则选择左6和右5的连接;

最终选择左2和右2的连接,左4和右3的连接,左6和右5的连接,满足最多不相交的情况

综上所看,所求最所不相交线的条数就是左右点连接关系的最长上升子序列。

注:此题的规模是40000,求最长上升子序列 O(N^2)的算法会超时,需要用到O(NlogN)

的算法。具体算法讲解参考博文:http://blog.csdn.net/lianai911/article/details/20554865

#include<cstdio>
using namespace std;
int a[40002],d[40002];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        int len=1;
        d[1] = a[1];
        for(int i=2;i<=n;i++)
        {
            if(d[len]<a[i])
            {
                d[++len] = a[i];
                continue;
            }
            int l=1,r=len,mid;
            while(l<=r)
            {
                mid = (l+r)/2;
                if(d[mid]<a[i])
                l = mid+1;
                else
                r = mid-1;
            }
            d[l] = a[i];
        }
        printf("%d\n",len);
    }
    return 0;
}


版权声明:本文为a17865569022原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a17865569022/article/details/78754409

智能推荐

单链表+单链表代码(链表最基础)

链表 链表是有顺序的表,在内存中存储: 链表是以节点的方式存储的 每个节点包括data域,next域:指向下一个节点 如图:发现链表的各个节点不一定是连续存放的,有跳跃的,不是连续存储 链表分为带头节点的链表和没有头结点的链表 添加: 1.先创建一个head头结点,作用就是单链表的头 2.后面每添加一个节点,就直接加入到链表最后 遍历: 代码 添加节点到链表里: 这里借助于temp节点,通过循环找...

Rtthread学习笔记(十三)RT-Thread Studio开启硬件看门狗Watchdog

一、开启硬件看门狗Watchdog 1、配置RT-Thread Settings 2、开启stm32f1xx_hal_conf.h中的宏定义 3.使用RT接口函数初始化硬件看门狗...

TYVJ 4864 天天去哪吃 || 清北学堂金秋杯大奖赛

题目描述: 记录一下i这个值上次出现的位置在哪里,就是pre...

java反编译

jvm 把Boolean类型的值flag当做int类型处理。​​​ Foo.java: 由 class 文件生成 jasm 文件:java -jar asmtools.jar jdis Foo.class > Foo.jasm  修改jasm文件: 执行反编译: java -jar jd-gui-1.6.6.jar File 打开Foo.class文件:b修改为2 重新执行java...

【学习笔记】03-v-html的学习和示例

v-html的认识和使用 示例: 显示结果: 注意:v-html是有复制的...

猜你喜欢

Java实现在线考试系统(系统介绍)

1.和现在有的考试系统有以下几种优势: a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已批阅试卷等。传统的考试系统划分并不细,业务功能简单。 b.和学校的考试系统还有外面的考试系统比较起来,本系统是B/S结构,学校的考试系统一般为C/S结构,性能方面不如B/S结构,并且C/S接口需要安装客户端,客户端压力很大,我的系统只需要电脑具有浏览器,在同一局域...

计算机视觉--多视几何初步尝试

基础矩阵的原理 K和K’分别是两个相机的参数矩阵。p和p’是X在平面π的坐标表示。所以可以得出 具体计算过程 代码: #!/usr/bin/env python coding: utf-8 from PIL import Image from numpy import * from pylab import * import numpy as np from imp ...

java初学者怎么学习才可以快速入门

java初学者怎么学习才可以快速入门 一、了解JAVA 我们要知道:Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言。 Java之父:詹姆斯·高斯林 1.1 java的三个体系 Java SE(Java Platform Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境...

字段属性之主键&增删改查&自增长&唯一键约束

字段属性之主键&自增长&唯一键约束 主键 主键:primary key 主要的键 一张表中只有一个字段可以使用对应的键,用来唯一的约束该字段里面的数据,不能重复,这种称之为主键 一张表只能最多一个主键 增加主键 SQL操作中有多种方式增加主键大体分为三种 1.在创建表的时候直接在字段之后跟primary key关键字(主键本身不允许为空) 优点:非常直接:缺点:只能使用一个字段作为...

linux下 基于libmad的socket多用户mp3音频在线播放服务器

在众多大神的帮助下,这个在线播放流媒体服务器终于完成啦。。。。 这个mp3流媒体服务器设计的思路是,服务器程序server用多线程实现和多个客户端的通信(这是必然的),然后发送给客户端当前的音频列表公客户端选择,之后根据k客户端的选择给多个客户端传输相应mp3文件的数据,同时,客户端进行实时地音频解码并播放。 关于libmad开源mp3音频解码库的使用,见上一篇博客吧。。。。 在服务器程序这一端,...