• <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
            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 閱讀(237) 評論(0)  編輯 收藏 引用 所屬分類: DP
            亚洲v国产v天堂a无码久久| 久久久噜噜噜久久中文字幕色伊伊| 久久精品国产99久久久香蕉| 国产午夜精品理论片久久| 一97日本道伊人久久综合影院| 一本久久a久久精品vr综合| 新狼窝色AV性久久久久久| 99久久综合国产精品二区| 久久天天躁狠狠躁夜夜不卡| 久久电影网2021| 久久人人爽人人爽人人片av麻烦 | 色妞色综合久久夜夜| 久久精品无码一区二区三区| 久久久久久A亚洲欧洲AV冫| 久久国产精品99精品国产| 四虎国产精品成人免费久久| 国产精品久久永久免费| 精品伊人久久大线蕉色首页| 久久黄视频| 国内精品久久久久久中文字幕 | 伊色综合久久之综合久久| 91精品国产91久久综合| 久久久久久久久久久久久久| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 中文字幕乱码久久午夜| 性做久久久久久免费观看| 丰满少妇人妻久久久久久4| 精品无码久久久久久尤物| 亚洲人成电影网站久久| 久久精品国产一区二区电影| 久久精品这里热有精品| 7777久久亚洲中文字幕| 国产亚洲美女精品久久久2020| 热久久国产欧美一区二区精品| 久久久久国产日韩精品网站| 成人a毛片久久免费播放| 久久青青草原精品影院| 国产 亚洲 欧美 另类 久久| 精品久久久久久国产免费了| 精品久久综合1区2区3区激情| 精品无码久久久久久久动漫|