• <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
            <2006年10月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217880
            • 排名 - 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題目
            久久亚洲精品无码AV红樱桃| 久久棈精品久久久久久噜噜| 国产精品永久久久久久久久久| 久久夜色精品国产亚洲| 天天久久狠狠色综合| 综合久久给合久久狠狠狠97色| 国产成人精品三上悠亚久久| 久久国产精品无码HDAV | 久久婷婷色综合一区二区| 亚洲中文字幕久久精品无码APP| 久久精品国产亚洲网站| 三级三级久久三级久久| 蜜桃麻豆www久久| 亚洲精品乱码久久久久久蜜桃不卡 | 99999久久久久久亚洲| 日本一区精品久久久久影院| 伊人 久久 精品| 国产999精品久久久久久| 久久久这里只有精品加勒比| 大美女久久久久久j久久| 亚洲国产精品无码久久久秋霞2 | 久久99国产精品成人欧美| 人妻少妇久久中文字幕一区二区| 久久精品无码一区二区三区日韩| 久久99精品久久只有精品| 国产成人精品综合久久久| 免费一级做a爰片久久毛片潮| 亚洲国产精品人久久| 国内精品久久久久久99蜜桃| 中文字幕人妻色偷偷久久| 久久这里有精品视频| 久久久久久无码Av成人影院| 欧美国产精品久久高清| 久久这里只有精品久久| 国产91久久精品一区二区| 久久久久亚洲精品天堂| 蜜臀av性久久久久蜜臀aⅴ| 久久成人国产精品免费软件| 久久午夜福利无码1000合集| 亚洲国产精品无码久久青草 | 久久人人爽人人爽人人AV|