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

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3187
            

              1#include <cstdio>
              2
              3const int SIZE = 101;
              4const int MAXS = 5000001;
              5
              6int N, M;
              7int food[SIZE], had[SIZE], need[SIZE];
              8int value[SIZE][2], cost[SIZE][2];
              9int arr[MAXS];
             10
             11int Cal(const int& p)
             12{
             13    int sum = 0;
             14    int v, x, y;
             15
             16    arr[0] = 0;
             17    for ( v = 1; v <= need[p] + value[p][1]; ++v )
             18    {
             19        arr[v] = -1;
             20    }
             21    for ( v = 0; v <= need[p] + value[p][1]; ++v )
             22    {
             23        x = value[p][0];
             24        y = value[p][1];
             25        if ( v - x >= 0 && arr[v - x] != -1 && (arr[v - x] + cost[p][0] < arr[v] || arr[v] == -1) )
             26            arr[v] = arr[v - x] + cost[p][0];
             27
             28        if ( v - y >= 0 && arr[v - y] != -1 && (arr[v - y] + cost[p][1] < arr[v] || arr[v] == -1) )
             29            arr[v] = arr[v - y] + cost[p][1];
             30        
             31    }
             32
             33    sum = MAXS;
             34    for ( v = need[p]; v <= need[p] + value[p][1]; ++v )
             35    {
             36        if ( arr[v] != -1 && arr[v] < sum )
             37            sum = arr[v];
             38    }
             39
             40    return sum;
             41}
             42bool Check(const int& limit)
             43{
             44    int i, C;
             45
             46    C = 0;
             47    for ( i = 0; i < N; ++i )
             48    {
             49        need[i] = food[i] * limit - had[i] ;
             50
             51        C += Cal(i);
             52
             53        if ( C > M )
             54            return false;
             55
             56    }
             57
             58    return true;
             59}
             60void Solve()
             61{
             62    int left = 1, right = M, mid;
             63
             64    while ( left <= right )
             65    {
             66        mid = (left + right) >> 1;
             67
             68        if ( Check(mid) )
             69            left = mid + 1;
             70        else
             71            right = mid - 1;
             72    }
             73
             74    printf("%d\n", left - 1);
             75}
             76
             77int main()
             78{
             79    freopen("1.txt", "r", stdin);
             80
             81    int i;
             82
             83    while ( true )
             84    {
             85        scanf("%d %d", &N, &M);
             86
             87        if ( N == 0 && M == 0 )
             88            break;
             89
             90        for ( i = 0; i < N; ++i )
             91        {
             92            scanf("%d %d", &food[i], &had[i]);
             93            scanf("%d %d %d %d", &value[i][0], &cost[i][0], &value[i][1], &cost[i][1]);
             94        }
             95
             96        Solve();
             97    }
             98
             99    return 0;
            100}
            

	
            
	
	
            
		posted on 2009-05-11 21:47 巫 閱讀(239) 評論(0)  編輯 收藏 引用  所屬分類: DP 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



狠狠精品干练久久久无码中文字幕|
日本福利片国产午夜久久|
精品久久久久久无码不卡|
亚洲欧美成人久久综合中文网|
一本色综合网久久|
国产激情久久久久影院老熟女免费|
亚洲美日韩Av中文字幕无码久久久妻妇
|
久久综合九色综合网站|
久久国产免费观看精品3|
亚洲欧美精品一区久久中文字幕|
久久精品国产亚洲AV高清热|
久久精品人妻一区二区三区|
亚洲精品白浆高清久久久久久|
久久99国产亚洲高清观看首页
|
91精品国产高清久久久久久国产嫩草
|
久久久久97国产精华液好用吗|
久久99久久99精品免视看动漫
|
久久国产精品99久久久久久老狼
|
久久免费看黄a级毛片|
国产精品美女久久久久av爽|
国产美女久久精品香蕉69|
亚洲精品久久久www|
国产精品伊人久久伊人电影|
久久精品国产亚洲77777|
久久精品视频一|
成人精品一区二区久久久|
无码超乳爆乳中文字幕久久|
久久丝袜精品中文字幕|
国产高清国内精品福利99久久|
久久99国产亚洲高清观看首页|
久久棈精品久久久久久噜噜|
久久久久久精品免费免费自慰|
深夜久久AAAAA级毛片免费看|
日本精品久久久久中文字幕|
久久国产精品一国产精品金尊|
日韩人妻无码一区二区三区久久|
久久久久青草线蕉综合超碰|
2021最新久久久视精品爱|
噜噜噜色噜噜噜久久|
婷婷久久综合九色综合九七|
午夜精品久久久久9999高清|