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

            gzwzm06

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks
             1#include <cstdio>
             2#include <cstring>
             3
             4const int SIZE = 101;
             5const int MAX = 1000001;;
             6
             7int M, N;
             8int arr[10][SIZE], size[10], sum[10];
             9char cloth[10][11];
            10bool dp[MAX];
            11
            12int GetType(const char* str)
            13{
            14    int i;
            15    for ( i = 0; i < M; ++i )
            16        if ( strcmp(str, cloth[i]) == 0 )
            17            break;
            18
            19    return i;
            20}

            21
            22void Solve()
            23{
            24    int i, v, n, t, limit;
            25    int time = 0;
            26
            27    for ( n = 0; n < M; ++n )
            28    {
            29        memset(dp, 0sizeof(dp));
            30        dp[0= true;
            31
            32        t = 0;
            33        limit = sum[n] >> 1;                //01背包:dp出最接近 sum / 2 的值
            34        for ( i = 0; i < size[n]; ++i )
            35        {
            36            for ( v = limit; v >= arr[n][i]; --v )
            37            {
            38                
            39                if ( dp[v - arr[n][i]] )
            40                {
            41                    dp[v] = true;            //對該位置標(biāo)志
            42                    if ( v > t )
            43                    {
            44                        t = v;
            45                    }

            46                }

            47
            48            }

            49        }

            50        
            51        time += (sum[n] - t);    //須取最大的值
            52    }

            53    
            54
            55    printf("%d\n", time);
            56}

            57
            58int main()
            59{
            60//    freopen("1.txt", "r", stdin);
            61
            62    int i, j, n;
            63    char str[11];
            64
            65    while ( scanf("%d %d"&M, &N) != EOF )
            66    {
            67        if ( M == 0 && N == 0 )
            68            break;
            69
            70        for ( i = 0; i < M; ++i )
            71        {
            72            size[i] = 0;
            73            sum[i] = 0;
            74            scanf("%s", cloth[i]);
            75        }

            76
            77        for ( i = 0; i < N; ++i )
            78        {
            79            scanf("%d %s"&n, str);
            80
            81            j = GetType( str );
            82            arr[j][size[j]++= n;
            83            sum[j] += n;
            84        }

            85
            86        Solve();
            87    }

            88
            89    return 0;
            90}
            posted on 2009-05-03 11:03 閱讀(408) 評論(0)  編輯 收藏 引用 所屬分類: DP
            久久精品成人免费国产片小草| 亚洲中文久久精品无码ww16| 色播久久人人爽人人爽人人片AV| 中文字幕亚洲综合久久| 久久精品一区二区三区中文字幕| 国产AⅤ精品一区二区三区久久| 合区精品久久久中文字幕一区| 亚洲精品国产字幕久久不卡| 国产真实乱对白精彩久久| 国产成人精品综合久久久| 91精品免费久久久久久久久| 无码国内精品久久综合88| 久久久av波多野一区二区| 久久综合视频网站| 69久久精品无码一区二区| 久久国产精品无| 久久久久一级精品亚洲国产成人综合AV区| 久久亚洲精品成人无码网站| 伊人久久综合热线大杳蕉下载| 亚洲精品无码久久千人斩| 久久福利资源国产精品999| 久久综合伊人77777| 久久精品这里只有精99品| 久久精品国产精品亚洲人人| 欧美激情精品久久久久| 国产精品成人久久久久三级午夜电影| 亚洲精品乱码久久久久久蜜桃不卡 | 久久免费大片| 一本久久免费视频| 91精品国产综合久久精品| 中文精品久久久久国产网址 | 久久久久亚洲精品日久生情 | 午夜人妻久久久久久久久| 久久精品国产亚洲av瑜伽| 蜜桃麻豆www久久国产精品| 精品综合久久久久久97| 久久人人爽爽爽人久久久| 国产精品18久久久久久vr | 久久精品国产亚洲网站| 三级韩国一区久久二区综合 | 国内精品久久久久久久久电影网|