• <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++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				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, 0, sizeof(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;            //對該位置標志
            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 巫 閱讀(412) 評論(0)  編輯 收藏 引用  所屬分類: DP 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



国产欧美久久一区二区|
久久久久亚洲AV成人网人人网站|
香蕉久久夜色精品升级完成|
国产精品99久久99久久久|
国产成人精品久久亚洲|
久久亚洲AV无码精品色午夜|
四虎国产精品免费久久5151|
97精品依人久久久大香线蕉97|
久久综合九色综合97_久久久|
亚洲伊人久久成综合人影院|
成人国内精品久久久久影院|
国产一区二区久久久|
久久成人18免费网站|
久久亚洲AV成人无码国产|
中文字幕无码av激情不卡久久|
久久久久久夜精品精品免费啦
|
国产精品久久久久久久人人看|
久久香蕉超碰97国产精品|
中文字幕无码久久久|
久久夜色精品国产|
久久99精品久久久久久水蜜桃
|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区
|
国产成人久久精品二区三区|
久久精品国产亚洲av麻豆小说|
久久夜色精品国产噜噜亚洲a|
精品久久久久久国产三级
|
久久99国产精品99久久
|
亚洲伊人久久成综合人影院
|
久久精品嫩草影院|
av国内精品久久久久影院|
午夜精品久久久久久毛片|
亚洲精品午夜国产VA久久成人|
国产偷久久久精品专区|
亚洲午夜久久久久妓女影院|
一本色道久久综合狠狠躁|
99久久精品国产一区二区|
亚洲AV日韩精品久久久久|
久久精品国产亚洲AV大全|
久久午夜电影网|
久久精品国产一区二区|
国内精品伊人久久久久妇|