gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

ZOJ 3187--Inviting Friends

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

#include <cstdio>
2

const int SIZE = 101;
4

const int MAXS = 5000001;
5

int N, M;
7

int food[SIZE], had[SIZE], need[SIZE];
8

int value[SIZE][2], cost[SIZE][2];
9

int arr[MAXS];
10

int Cal(const int& p)
12

{
13

int sum = 0;
14

int v, x, y;
15

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

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

}
32

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

return sum;
41

}
42

bool Check(const int& limit)
43

{
44

int i, C;
45

C = 0;
47

for ( i = 0; i < N; ++i )
48

{
49

need[i] = food[i] * limit - had[i] ;
50

C += Cal(i);
52

if ( C > M )
54

return false;
55

}
57

return true;
59

}
60

void Solve()
61

{
62

int left = 1, right = M, mid;
63

while ( left <= right )
65

{
66

mid = (left + right) >> 1;
67

if ( Check(mid) )
69

left = mid + 1;
70

else
71

right = mid - 1;
72

}
73

printf("%d\n", left - 1);
75

}
76

int main()
78

{
79

freopen("1.txt", "r", stdin);
80

int i;
82

while ( true )
84

{
85

scanf("%d %d", &N, &M);
86

if ( N == 0 && M == 0 )
88

break;
89

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

Solve();
97

}
98

return 0;
100

}

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

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 7th GDCPC Problem G: Black Jack ZOJ 3187--Inviting Friends zoj 3201 Tree of tree POJ 3211 Washing Clothes POJ 3254 Corn Fields POJ 3670 Eating Together(最長非遞增（非遞減）子序列) POJ 3661-Running Pku 3494--Largest Submatrix of All 1’s(路徑壓縮) PKU 1964--City Game(棧模擬) POJ 2559--Largest Rectangle in a Histogram(棧模擬)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論