• <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年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217855
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Bugs Integrated, Inc.
            Time Limit:15000MS  Memory Limit:30000K
            Total Submit:1180 Accepted:309
            Case Time Limit:5000MS

            Description
            Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.


            Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
            Task
            You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

             

            Input
            The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

            Output
            For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

            Sample Input

            2
            6 6 5
            1 4
            4 6
            2 2
            3 6
            6 4
            6 5 4
            3 3
            6 1
            6 2
            6 4
            

             

            Sample Output

            3
            4

             

            Source
            CEOI 2002

            CODE:

            #include <iostream>
            using namespace std;

            int g[150][10], blk[10];
            int d[4][60000];
            int e[11= {1392781243729218765611968359049};
            int n, m, kn;
            int can1, can2, b[10][60000];
            int *l0, *l1, *l2, *l3, *bit0, *bit1, *bit2;

            void build() {
                
            int i, j, tmp;
                
            for (i=0; i<e[10]; i++{
                    j 
            = 0; tmp = i;
                    
            while (tmp > 0{
                        b[j][i] 
            = tmp % 3;
                        tmp 
            /= 3;
                        j
            ++;
                    }

                }

            }
             

            inline 
            int maxt(int a, int b) {
                
            return a > b ? a : b;
            }


            void solve() {
                
            int i, j, k, x, y, a1, a2, p, c;
                scanf(
            "%d%d%d"&n, &m, &kn);
                memset(g, 
            0sizeof(g));
                memset(d, 
            0sizeof(d));
                
            for (i=0; i<kn; i++{
                    scanf(
            "%d%d"&x, &y);
                    g[x
            -1][y-1= 1;
                }

                
            for (i=0; i<m; i++) blk[i] = 1 - g[0][i];
                
            for (i=1, c=2; i<n; i++{
                    
            for (j=0; j<m; j++{
                        
            if (g[i][j]) blk[j] = 0;
                        
            else blk[j]++;
                        c 
            = (c+1)%4;
                        can1 
            = (j>0 && blk[j]>2 && blk[j-1]>2);
                        can2 
            = (j>1 && blk[j]>1 && blk[j-1]>1 && blk[j-2]>1);
                        a1 
            = 2*e[j]+2*e[j-1];
                        a2 
            = e[j]+e[j-1]+e[j-2];
                        l0 
            = d[c]; l1 = d[(c+3)%4]; l2 = d[(c+2)%4]; l3 = d[(c+1)%4];
                        bit0 
            = b[j]; 
                        
            if (j>0) bit1 = b[j-1]; 
                        
            if (j>1) bit2 = b[j-2];
                        
            for (p=0; p<e[m]; p++{
                            
            if (bit0[p]) {
                                l0[p] 
            = l1[p-e[j]];
                            }
             else {
                                l0[p] 
            = l1[p];
                                
            if (j>0 && !bit1[p]) {
                                    
            if (can1) l0[p] = maxt(l0[p],l2[p+a1]+1);
                                    
            if (can2 && !bit2[p]) l0[p] = maxt(l0[p], l3[p+a2]+1);
                                }

                            }

                        }

                    }

                }

                printf(
            "%d\n", d[c][0]);
            }


            int main() {
                build();
                
            int caseTime;
                scanf(
            "%d"&caseTime);
                
            while (caseTime--{
                    solve();
                }

                
            return 0;
            }


             
            posted on 2007-04-18 11:42 閱讀(1781) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            国产精品伊人久久伊人电影| 日韩中文久久| 久久午夜伦鲁片免费无码| 欧美日韩久久中文字幕| 久久99精品久久久大学生| 热re99久久6国产精品免费| 日本久久久久亚洲中字幕| 99精品国产在热久久无毒不卡| 中文字幕亚洲综合久久2| 精品乱码久久久久久夜夜嗨 | 精品久久久噜噜噜久久久| 久久综合九色综合久99| 久久婷婷色香五月综合激情| 亚洲人成网亚洲欧洲无码久久 | 国产精品免费看久久久香蕉| 久久亚洲AV成人无码| 狠狠色丁香婷综合久久| 中文字幕无码av激情不卡久久| 国产亚洲色婷婷久久99精品| 久久狠狠爱亚洲综合影院 | 四虎国产精品免费久久久| 久久综合国产乱子伦精品免费| 国产精品成人精品久久久| 国产精品女同久久久久电影院| 人妻精品久久久久中文字幕| 色噜噜狠狠先锋影音久久| 久久久免费精品re6| 久久久久久久91精品免费观看 | 免费精品久久久久久中文字幕| 丁香狠狠色婷婷久久综合| 一本色综合网久久| 久久精品国产免费观看三人同眠| 国产精品VIDEOSSEX久久发布 | 亚洲国产香蕉人人爽成AV片久久| 精品久久久久久国产91| 亚洲国产精品久久久天堂| 久久久www免费人成精品| 久久九九久精品国产免费直播| 日本亚洲色大成网站WWW久久 | 久久99热这里只有精品66| 亚洲国产精品成人久久蜜臀|