• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書(shū)研究!

            常用鏈接

            留言簿(19)

            隨筆分類(lèi)(81)

            文章分類(lèi)(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217919
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            解題報(bào)告:http://www.mydrs.org/program/list.asp?id=583

            Bridging Signals

            Time limit: 1 Seconds?? Memory limit: 32768K??
            Total Submit: 946?? Accepted Submit: 495??

            '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?

            Figure 1. To the left: The two blocks' ports and their signal mapping (4, 2, 6, 3, 1, 5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.

            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 ith number specifies which port on the right side should be connected to the ith 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 ith line is the port number of the block on the right side which should be connected to the ith 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

            #include? < iostream>
            using
            ? namespace?std;

            const ? int ?MAXN? = ? 40001;

            void?Solve()
            {
            ????
            int?n;
            ????
            int?i,?j,?k;
            ????
            int?l,?r,?m;
            ????
            int?t;
            ????
            int ?d[MAXN]? = ? { 0 };
            ????
            int?a[MAXN];
            ????
            int ?len? = ? 0;
            ????scanf(
            " %d " ,? &n);
            ????
            for ?(i = 1 ;?i <= n;?i ++)?
            ????????scanf(
            " %d " ,? &a[i]);
            ????
            for ?(i = 1 ;?i <= n;?i ++)
            ????
            {
            ????????
            if ?(a[i]? >?d[len])
            ????????
            {
            ????????????len?
            += ? 1;
            ????????????d[len]?
            =?a[i];
            ????????}

            ????????
            else
            ????????
            {
            ????????????l?
            = ? 1;
            ????????????r?
            =?len;
            ????????????
            while ?(l? < ?r? - ? 1)
            ????????????
            {
            ????????????????m?
            = ?(l? + ?r)? / ? 2;
            ????????????????
            if ?(d[m]? <?a[i])
            ????????????????????l?
            =?m;
            ????????????????else
            ????????????????????r?
            =?m;
            ????????????}

            ????????????if
            ?(d[l]?>?a[i])?
            ????????????????d[l]?
            =?a[i];
            ????????????else
            ????????????????d[r]?
            =?a[i];
            ????????}

            ????}

            ????printf("
            %d\n ",?len);????????
            }



            int?main()
            {
            ????
            int?caseTime;
            ????scanf(
            " %d " ,? &caseTime);
            ????
            while ?(caseTime -- ? != ? 0)
            ????
            {
            ????????Solve();
            ????}

            ????system("pause
            ");
            ????
            return ?0;
            }






            posted on 2006-10-04 12:20 閱讀(585) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): ACM題目
            久久99久国产麻精品66| 久久国产热这里只有精品| 国内精品伊人久久久久妇| 99久久这里只精品国产免费| 色妞色综合久久夜夜| 久久天堂电影网| 久久精品中文字幕一区| 国产精品乱码久久久久久软件| 亚洲国产另类久久久精品黑人 | 久久免费观看视频| 精品一二三区久久aaa片| 日本道色综合久久影院| 亚洲色欲久久久综合网东京热| 国产精品激情综合久久| 久久久久人妻一区精品色 | 亚洲国产精品无码久久久蜜芽 | av午夜福利一片免费看久久| 精品无码久久久久久久动漫| 99久久国产综合精品女同图片| 成人精品一区二区久久| 久久99亚洲网美利坚合众国| 香港aa三级久久三级老师2021国产三级精品三级在 | 亚洲香蕉网久久综合影视| 久久99精品国产麻豆不卡| 国产成人久久激情91| 人妻无码αv中文字幕久久| 久久综合久久综合亚洲| 久久久人妻精品无码一区| 国产精品成人99久久久久| 99久久精品费精品国产一区二区| 人人妻久久人人澡人人爽人人精品| 精品久久综合1区2区3区激情| 91精品国产高清久久久久久io | 日韩精品无码久久一区二区三| 久久国产免费观看精品3| 久久久久亚洲AV成人片| 久久久无码一区二区三区 | 亚洲天堂久久久| 国产激情久久久久久熟女老人 | 久久精品天天中文字幕人妻| 人人狠狠综合久久88成人|