• <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>
            posts - 74,  comments - 33,  trackbacks - 0

            Description

            The cows have revised their game of leapcow. They now play in the middle of a huge pasture upon which they have marked a grid that bears a remarkable resemblance to a chessboard of N rows and N columns (3 <= N <= 365).

            Here's how they set up the board for the new leapcow game:

            * First, the cows obtain N x N squares of paper. They write the integers from 1 through N x N, one number on each piece of paper.

            * Second, the 'number cow' places the papers on the N x N squares in an order of her choosing.

            Each of the remaining cows then tries to maximize her score in the game.

            * First, she chooses a starting square and notes its number.

            * Then, she makes a 'knight' move (like the knight on a chess board) to a square with a higher number. If she's particularly strong, she leaps to the that square; otherwise she walks.

            * She continues to make 'knight' moves to higher numbered squares until no more moves are possible.

            Each square visited by the 'knight' earns the competitor a single point. The cow with the most points wins the game.

            Help the cows figure out the best possible way to play the game.

            Input

            * Line 1: A single integer: the size of the board

            * Lines 2.. ...: These lines contain space-separated integers that tell the contents of the chessboard. The first set of lines (starting at the second line of the input file) represents the first row on the chessboard; the next set of lines represents the next row, and so on. To keep the input lines of reasonable length, when N > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.

            Output

            * Line 1: A single integer that is the winning cow's score; call it W.

            * Lines 2..W+1: Output, one per line, the integers that are the starting square, the next square the winning cow visits, and so on through the last square. If a winning cow can choose more than one path, show the path that would be the 'smallest' if the paths were sorted by comparing their respective 'square numbers'.

            Sample Input

            4
            1 3 2 16
            4 10 6 7
            8 11 5 12
            9 13 14 15

            Sample Output

            72459101213
            本以為最長上升子序列,沒錯,最長的步數對了,但是因為路徑更新有無,所以還是一直Wrong Answer。。。。無語

            
            

             

            代碼AC后更新

            posted on 2008-12-23 21:52 KNIGHT 閱讀(378) 評論(2)  編輯 收藏 引用

            FeedBack:
            # re: poj 2111 Millenium Leapcow
            2008-12-23 23:22 | Knight
            如果你能接受這個
            3160K 1047MS C++ 1547B
            真的很煩,居然1047ms一般都是200ms左右我居然這么多,暈
            思路還是最長上升子序列
            不過更新路徑的函數代碼如下
            int cmp(int a,int b)
            {
            if(pre[a]==a)
            {
            if(a>b)return 1;
            else if(a==b)return 0;
            else return -1;
            }
            else
            {
            int t=cmp(pre[a],pre[b]);
            if(t==0)
            {
            if(a>b)return 1;
            else if(a==b)return 0;
            else return -1;
            }
            else return t;
            }
            }
            ********************************
            即如果路徑長度相同的話,就執行cmp從而判斷字典序!更新字典序!很浪費時間!
            ********************************  回復  更多評論
              
            # re: poj 2111 Millenium Leapcow
            2008-12-24 12:43 | Knight
            魷魚大牛的思路
            從n*n開始搜索到1結束DP更新路徑
            排名20 3160K 157MS C++ 1228B
            還行經典代碼如下:
            for(i=M;i>=1;i--)
            {
            for(j=0;j<8;j++)
            {
            int x=num[i].x+dir[j][0];
            int y=num[i].y+dir[j][1];
            if(OK(x,y,i))
            {
            if(num[i].max+1>num[map[x][y]].max)
            {
            num[map[x][y]].max=num[i].max+1;
            pre[map[x][y]]=i;
            }
            else if(num[i].max+1==num[map[x][y]].max&&i<pre[map[x][y]])
            pre[map[x][y]]=i;
            }
            }
            if(MAX<=num[i].max)
            {
            MAX=num[i].max;
            sign=i;
            }
            }  回復  更多評論
              
            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            人妻无码αv中文字幕久久| 日韩人妻无码一区二区三区久久| 国产亚洲精久久久久久无码| 久久久久久国产精品无码超碰| 人妻精品久久久久中文字幕一冢本| 久久夜色精品国产噜噜噜亚洲AV| 91精品国产综合久久婷婷| 97精品久久天干天天天按摩 | 久久久久亚洲AV成人网人人软件| 狠狠人妻久久久久久综合蜜桃| 国产精品久久新婚兰兰| 国产91久久精品一区二区| 久久青青草原精品国产软件 | 亚洲精品乱码久久久久久蜜桃图片 | 久久久久AV综合网成人| 久久青青草原精品国产软件| 日韩精品久久久久久免费| 久久亚洲中文字幕精品一区| 久久精品毛片免费观看| 亚洲美日韩Av中文字幕无码久久久妻妇 | 亚洲精品tv久久久久久久久久| 精品熟女少妇AV免费久久| 久久午夜福利电影| 色综合久久最新中文字幕| 国产精品免费看久久久| 亚洲愉拍99热成人精品热久久| 久久国产三级无码一区二区| 国产午夜精品理论片久久影视 | 久久播电影网| 国产成人综合久久久久久| 久久久久综合网久久| 国产精品久久久久天天影视| 日本欧美久久久久免费播放网| 亚洲国产精品无码久久青草| 久久久久这里只有精品| 久久www免费人成精品香蕉| 国产精品午夜久久| 久久人妻少妇嫩草AV蜜桃| 久久99精品久久久久久水蜜桃| 草草久久久无码国产专区| 久久国产免费直播|