gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
ZOJ 3187--Inviting Friends
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 巫 阅读(218) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理