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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2009 Moo University - Emergency Pizza Order 無恥貪心解法

            這題能不能貪心,是很難說的。。
            因為沒有能什么證明貪心是對的,但也沒找到什么反例。
            代碼寫出來,WA了。
            但總覺得是對的,因為嗎的實在找不到反例。
            結果找到數據測了下,果然十個過了九個。。
            你看,如果這是NOIP,跟滿分都沒啥區別的對吧。我已經滿足了。。
            沒過的那組,比較大,肉眼看不出是啥問題。
            想了下,給排序加多了一個判斷,然后那組數據就過了。。
            然后提交,嗎的還上榜了。。無語。

            這樣做比較無恥,網上有人說用最大流做,不理解。下次想一想。

            思路:
            如果牛喜歡的種類個數小于 K,那這種牛是無法滿足的。。
            把牛按照喜歡的種類個數排序,先處理小的。
            就是用組合數枚舉每一種可能的 pizza 情況。
            用 hash 保存這些情況。

            代碼:
            #include <stdio.h>
            #include 
            <stdlib.h>

            #define HASH_SIZE 65536

            struct cow_node {
                
            int val, cnt;
            }
            ;

            int C, T, K, ans;
            struct cow_node cows[1024];
            int hash[HASH_SIZE];

            int cmp(const void *a, const void *b)
            {
                
            if (((struct cow_node *)a)->cnt == ((struct cow_node *)b)->cnt)
                    
            return ((struct cow_node *)a)->val - ((struct cow_node *)b)->val;
                
            return ((struct cow_node *)a)->cnt - ((struct cow_node *)b)->cnt;
            }


            inline 
            int insert(int val)
            {
                
            int i, h;

                h 
            = val & (HASH_SIZE - 1);
                
            for (i = h + 1; i != h && hash[i] && hash[i] != val; )
                    i 
            = (i + 1& (HASH_SIZE - 1);
                
            if (i == h || hash[i] == val)
                    
            return 0;
                hash[i] 
            = val;
                
            return 1;
            }


            inline 
            int calc(struct cow_node *t)
            {
                
            int arr[32], map[32], i, j, val;

                
            for (i = j = 0; i < 32; i++)
                    
            if (t->val & (1 << i))
                        map[j
            ++= (1 << i);
                
            for (i = 0; i < K; i++)
                    arr[i] 
            = i;
                
            while (1{
                    val 
            = 0;
                    
            for (i = 0; i < K; i++)
                        val 
            |= map[arr[i]];
                    
            if (insert(val))
                        
            return 1;
                    
            for (i = K - 1; i >= 0 && arr[i] == i + t->cnt - K; i--);
                    
            if (i < 0)
                        
            break;
                    arr[i]
            ++;
                    
            for (i++; i < K; i++)
                        arr[i] 
            = arr[i - 1+ 1;
                }


                
            return 0;
            }


            int main()
            {
                
            int i, j, k;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d%d"&C, &T, &K);
                
            for (i = 0; i < C; i++{
                    scanf(
            "%d"&cows[i].cnt);
                    cows[i].val 
            = 0;
                    
            for (j = 0; j < cows[i].cnt; j++{
                        scanf(
            "%d"&k);
                        k
            --;
                        cows[i].val 
            |= 1 << k;
                    }

                    
            if (cows[i].cnt < K) {
                        i
            --; C--;
                        
            continue;
                    }

                }

                qsort(cows, C, 
            sizeof(cows[0]), cmp);

                
            for (i = 0; i < C; i++
                    ans 
            += calc(&cows[i]);
                printf(
            "%d\n", ans);

                
            return 0;
            }


            posted on 2010-04-27 14:25 糯米 閱讀(805) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            国产亚洲精午夜久久久久久| 国产精品99久久久久久www| 久久人妻AV中文字幕| 伊人久久大香线蕉精品不卡| 国产精品一区二区久久精品涩爱 | 亚洲香蕉网久久综合影视| 亚洲精品白浆高清久久久久久 | 国产成人精品白浆久久69| 草草久久久无码国产专区| 久久午夜福利无码1000合集| 国产精品九九九久久九九| 久久国产成人| 日韩人妻无码一区二区三区久久| www.久久热.com| 午夜不卡久久精品无码免费| 久久无码av三级| 99精品国产综合久久久久五月天| 久久99热国产这有精品| 伊人久久无码精品中文字幕| 51久久夜色精品国产| 天堂久久天堂AV色综合| 亚洲国产视频久久| 久久久久免费视频| 精品人妻伦九区久久AAA片69 | 久久久精品无码专区不卡| 日韩AV无码久久一区二区| 99久久这里只精品国产免费| 999久久久国产精品| 国产精品一区二区久久| 久久国产精品无码一区二区三区| 久久笫一福利免费导航| 日韩十八禁一区二区久久| 激情久久久久久久久久| 94久久国产乱子伦精品免费| 亚洲国产精品婷婷久久| 狠狠色丁香婷婷久久综合不卡| 亚洲AV无码久久寂寞少妇| 亚洲精品乱码久久久久久自慰| 中文字幕热久久久久久久| 久久国产欧美日韩精品| 人妻少妇久久中文字幕|