• <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

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217948
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Giftbox
            Time Limit:4000MS? Memory Limit:131072K
            Total Submit:1210 Accepted:218

            Description

            Bobobo and Bottle are good friends, and the birthday of Bottle is coming. So Bobobo is considering preparing Bottle an unexpected gift for his birthday. As a common sense that when a person at his or her birthday party, he or she will open the gift with the presence of the person who gives the gift and then expresses the appreciation. Bobobo knows that the characteristic of Bottle is rush when he receives something important, so he wants to play a joke on him in this way…

            Bobobo comes into a gift shop, and there are a lot of different kinds of gift boxes. Bobobo intends to choose various boxes with different size and choose one of the gift boxes to contain the precious gift and place this box into another bigger box and place this bigger box into another bigger one… So Bottle will not see the gift until he opens the innermost box. Imagine the process of his opening the boxes, how rush Bottle will be ^_^ !

            The gift boxes are n-dimensional. An n-dimensional box with dimensions ( X1, X2, …, Xn ) can be put into another box with dimensions ( Y1, Y2, …, Yn ) if there exists a permutation π on { 1, 2, …, n } such that Xπ1 < Y1, Xπ2 < Y2, …, Xπn < Yn. The gift is also n-dimensional and it can be put into a box if it satisfies the criterion above. And Bobobo must try his best to choose as many as boxes to contain the gift.

            Input

            The input file contains multiple test cases. The first line of each test case contains two numbers. The first one is a positive integer number N (1 ≤ N ≤ 500), the number of boxes in the gift shop, and the second one is a positive number d (3 ≤ d ≤ 1 000), the dimension of all the boxes. The next one line contains d positive integers ( G1, G2, …, Gd ) representing the dimensions of the gift. And the subsequent N lines each contain d positive integers ( X1, X2, …, Xd ) representing the dimensions of each box. You may assume that all the numbers you encounter are positive integers and less than 231. The input data is terminated by EOF.

            Output

            The output of each test case will contain only one line. Output the maximum number of the boxes that Bobobo can choose. If Bobobo can not find any box which can contain the gift, output “Please look for another gift shop!”

            Sample Input

            5 7
            4 6 8 2 7 5 3
            2 8 13 6 10 9 4
            80 70 12 3 6 8 2
            8 7 4 6 9 10 12
            100 200 300 400 500 600 700
            800 800 800 800 800 800 800

            Sample Output

            3

            Source
            POJ Monthly--2006.09.29, sza

            ?

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

            const ? int ?MAXN? = ? 510 ;
            const ? int ?MAXM? = ? 1010 ;

            int ?n,?m;
            int ?data[MAXN][MAXM];
            int ?map[MAXN][MAXN];
            int ?i,?j,?k;
            int ?f[MAXN];
            int ?d[MAXN];
            int ?ans;

            int ?DP( int ?b)
            {
            ????
            if ?(d[b]? > ? 0 )? return ?d[b];
            ????
            int ?i;
            ????
            int ?t? = ? 0 ;
            ????
            for ?(i = 1 ;?i <= n;?i ++ )
            ????
            {
            ????????
            if ?(f[i]? && ?b? != ?i? && ?map[b][i]? && ?t? < ?DP(i)? + ? 1 )?t? = ?DP(i)? + ? 1 ;
            ????}

            ????d[b]?
            = ?t;
            ????
            return ?d[b];
            }


            int ?main()
            {???
            ????
            while ?(scanf( " %d%d " ,? & n,? & m)? != ?EOF)
            ????
            {
            ????????
            for ?(i = 0 ;?i <= n;?i ++ )
            ????????
            {
            ????????????
            for ?(j = 0 ;?j < m;?j ++ )
            ????????????????scanf(
            " %d " ,? & data[i][j]);
            ????????????sort(data[i],?data[i]
            + m);
            ????????}

            ????????
            ????????memset(f,?
            1 ,? sizeof (f));
            ????????
            ????????
            for ?(i = 1 ;?i <= n;?i ++ )
            ????????????
            for ?(j = 0 ;?j < m;?j ++ )
            ????????????????
            if ?(data[i][j]? <= ?data[ 0 ][j])
            ????????????????
            {
            ????????????????????f[i]?
            = ? 0 ;
            ????????????????????
            break ;
            ????????????????}

            ????????????????
            ????????
            for ?(i = 0 ;?i <= n;?i ++ )
            ????????????
            for ?(j = 1 ;?j <= n;?j ++ )
            ????????????
            {
            ????????????????map[i][j]?
            = ? 1 ;
            ????????????????
            for ?(k = 0 ;?k < m;?k ++ )
            ????????????????
            {
            ????????????????????
            if ?(data[i][k]? >= ?data[j][k])
            ????????????????????
            {
            ????????????????????????map[i][j]?
            = ? 0 ;
            ????????????????????????
            break ;
            ????????????????????}

            ????????????????}

            ????????????}

            ????????????
            ????????memset(d,?
            0 ,? sizeof (d));

            ????????ans?
            = ?DP( 0 );

            ????????
            if ?(ans? == ? 0 )
            ????????????printf(
            " Please?look?for?another?gift?shop!\n " );
            ????????
            else
            ????????????printf(
            " %d\n " ,?ans);
            ???????????????????????
            ????}

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

            posted on 2006-09-30 01:46 閱讀(521) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            99久久精品费精品国产| 国产精品久久亚洲不卡动漫| 欧洲国产伦久久久久久久 | 99久久婷婷国产综合亚洲| 亚洲国产欧美国产综合久久| 国产精品99精品久久免费| 久久免费香蕉视频| 久久精品夜夜夜夜夜久久| 久久久久久av无码免费看大片| 久久婷婷是五月综合色狠狠| 日日噜噜夜夜狠狠久久丁香五月| 99久久国产热无码精品免费久久久久| 亚洲午夜无码AV毛片久久| 97久久精品国产精品青草| 亚洲午夜无码久久久久小说| 久久免费精品一区二区| 狠狠色狠狠色综合久久| 女同久久| 久久se精品一区精品二区国产| 人妻丰满AV无码久久不卡| 欧美日韩精品久久久久| 99久久精品国产毛片| 99久久人妻无码精品系列 | 久久精品无码一区二区三区| 国产精品久久婷婷六月丁香| 久久免费大片| 久久久久99精品成人片牛牛影视 | 四虎国产精品免费久久5151 | 久久久久国产一区二区| 久久91亚洲人成电影网站| 色偷偷偷久久伊人大杳蕉| 久久人人爽人人人人爽AV | 久久Av无码精品人妻系列| 亚洲精品美女久久久久99| 国产成人久久精品一区二区三区| 欧美久久久久久午夜精品| 国产精品女同一区二区久久| 狠狠色丁香婷综合久久| 人人狠狠综合久久亚洲88| 岛国搬运www久久| 日韩va亚洲va欧美va久久|