• <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热成人精品免费久久| 久久激情亚洲精品无码?V| 三上悠亚久久精品| 日韩人妻无码一区二区三区久久| 色婷婷久久综合中文久久蜜桃av| 嫩草影院久久国产精品| 欧洲国产伦久久久久久久| 天天爽天天狠久久久综合麻豆| aaa级精品久久久国产片| 亚洲欧美日韩久久精品| 99久久精品国内| 久久天天躁夜夜躁狠狠躁2022| 久久综合丝袜日本网| 久久久久亚洲av无码专区 | 久久99国产一区二区三区| 久久久久久久91精品免费观看| 精品国产乱码久久久久久郑州公司| 国内精品伊人久久久久网站| 色婷婷综合久久久中文字幕| 久久久久亚洲av成人无码电影| 99久久99这里只有免费费精品| 久久精品国产亚洲AV不卡| 狠狠干狠狠久久| 久久亚洲国产成人精品性色| 久久99这里只有精品国产| 成人精品一区二区久久| 国产成人精品久久免费动漫| 久久人人添人人爽添人人片牛牛| 国产视频久久| 久久精品亚洲男人的天堂| 久久久久久a亚洲欧洲aⅴ| 精品永久久福利一区二区| 亚洲AV日韩精品久久久久| 人人狠狠综合久久88成人| 久久精品国产亚洲AV蜜臀色欲| 久久亚洲国产成人精品无码区| 久久男人AV资源网站| 国产伊人久久| 亚洲国产综合久久天堂| 久久强奷乱码老熟女| 伊人久久无码精品中文字幕|