Untitled
unknown
plain_text
2 years ago
14 kB
7
Indexable
lịch trình quảng cáo
Một cửa hàng cần hiển thị quảng cáo 3 lần một ngày.
Tuy nhiên, họ chỉ có 1 bảng điện để hiển thị quảng cáo nên nên chọn thời điểm hiển thị quảng cáo sao cho khách xem được nhiều nhất có thể.
Khi khách xem quảng cáo, họ có thể nhận được số điểm được tính như sau:
1. Ba Quảng cáo có độ dài L1, L2, L3 và số điểm mà một người có thể nhận được sau khi xem chúng là P1, P2, P3.
2. Khách truy cập chỉ có thể nhận được điểm của Quảng cáo khi họ xem hết Quảng cáo đó (từ đầu đến cuối Quảng cáo đó)
3. Khi một khách truy cập xem nhiều Quảng cáo và đồng thời nhận được điểm cho họ, thì chỉ những Quảng cáo có điểm cao nhất mới được trao cho người đó.
4. Mỗi lần chỉ được hiển thị một Quảng cáo trên bảng điện (Nhưng Quảng cáo tiếp theo có thể hiển thị ngay sau khi Quảng cáo trước đó kết thúc)
Cho biết độ dài của mỗi Quảng cáo L1, L2, L3 và số điểm đạt được cho chúng P1, P2, P3, thời gian đến của mỗi khách vào cửa hàng và thời gian họ ở lại cửa hàng, hãy viết chương trình để chọn thời gian hiển thị quảng cáo sao cho càng nhiều điểm càng tốt cho khách truy cập. In ra tổng số điểm mà khách truy cập có thể nhận được.
Ví dụ : Có 7 khách vào quán với thời gian đến và ở như sau
Khách 1
Khách 2
Khách 3
Khách 4
Khách 5
Khách 6
Khách 7
Thời gian đến
2
6
3
7
1
2
1
Khoảng thời gian
2
4
3
2
1
1
10
Chiều dài
điểm
quảng cáo 1
1
1
quảng cáo 2
2
2
quảng cáo 3
3
3
Giả sử rằng Quảng cáo 1 được hiển thị ở thời điểm 2, Quảng cáo 2 ở thời điểm 7 và Quảng cáo 3 ở thời điểm 3, khách truy cập sẽ xem quảng cáo theo lịch trình bên dưới:
Khách 1
Khách 2
Khách 3
Khách 4
Khách 5
Khách 6
Khách 7
Quảng cáo 1
Đồng hồ
-
-
-
-
Đồng hồ
Đồng hồ
Quảng cáo 2
-
Đồng hồ
-
Đồng hồ
-
-
Đồng hồ
Quảng cáo 3
-
-
Đồng hồ
-
-
-
Đồng hồ
(Lưu ý rằng khách truy cập 1 đã không xem hết Ads3, vì vậy điểm của Ads3 không được trao cho anh ta)
Số điểm mà mỗi khách truy cập có thể nhận được khi xem Quảng cáo được hiển thị như sau:
Khách 1
Khách 2
Khách 3
Khách 4
Khách 5
Khách 6
Khách 7
Quảng cáo 1
1
-
-
-
-
1
1
Quảng cáo 2
-
2
-
2
-
-
2
Quảng cáo 3
-
-
3
-
-
-
3
Tổng cộng 12 Điểm
1
2
3
2
0
1
3
(Khách 7 đã xem đầy đủ tất cả các Quảng cáo, tuy nhiên anh ta chỉ có thể nhận được điểm cao nhất của một Quảng cáo - tức là 3 điểm của Quảng cáo 3)
Có nhiều cách để sắp xếp thời gian hiển thị và phương pháp trên cho chúng ta tổng số điểm tối đa mà khách truy cập có thể nhận được, vì vậy câu trả lời trong trường hợp này là 12.
[ Ràng buộc ]
- Số lượng khách N (1 ≤ N ≤ 50)
- Thời gian đến Ai, khoảng thời gian Di của mỗi khách và độ dài của mỗi Quảng cáo L1, L2, L3 được cho dưới dạng số nguyên (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)
- Ái + Dị ≤ 50
- L1 + L2 + L3 ≤ 50
- Thời gian bắt đầu của một Quảng cáo : 1 ≤ thời gian bắt đầu ≤ 50
- P1, P2, P4 là các số nguyên (1 ≤ P1, P2, P3 ≤ 1000)
[ Đầu vào ]
Dòng 1 ghi T - tổng số TC (T ≤ 50)
Trong mỗi TC:
- Dòng thứ nhất ghi N, L1, L2, L3, P1, P2, P3 theo thứ tự
- N dòng tiếp theo: mỗi dòng ghi thời gian đến Ai và thời gian Di của từng khách
5 // Số test T=5
7 1 2 3 1 2 3 // Test case 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3
2 2 // A1 = 2, D1 = 2
6 4 //...
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
...
[ Đầu ra ]
Out đưa ra tổng số điểm tối đa mà khách truy cập có thể nhận được khi xem quảng cáo.
Trường hợp 1
12
Trường hợp #2
18
Trường hợp #3
17
Trường hợp #4
16
Trường hợp #5
17998
////////////input
50
7 1 2 3 1 2 3
2 2
6 4
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
3 1 2 3 7 6 4
10 1
11 2
13 3
5 2 2 1 2 5 4
2 4
4 6
9 1
14 10
30 15
50 31 4 1 734 134 546
1 39
4 28
9 24
12 16
7 29
6 27
12 14
24 18
1 34
11 20
5 23
31 16
12 38
3 35
10 2
35 14
11 34
31 13
6 14
10 7
4 17
15 19
7 36
8 19
13 20
7 18
27 6
9 5
13 14
2 20
9 12
5 13
34 12
5 20
17 7
18 31
33 6
14 8
4 6
10 38
23 10
36 13
17 15
27 20
11 21
27 1
31 13
20 16
47 2
19 26
6 3 4 3 12 9 10
1 3
4 4
8 4
7 4
8 3
1 4
6 1 3 1 11 3 11
17 24
28 7
20 30
4 46
16 6
1 47
6 1 5 2 34 30 17
20 10
1 22
13 2
27 8
8 41
16 33
3 2 3 2 38 43 5
19 4
8 33
11 36
1 2 3 1 19 43 38
11 11
14 2 2 1 70 71 44
11 23
8 26
10 36
17 31
30 12
27 8
33 10
3 32
28 2
8 12
22 26
4 21
15 15
1 13
7 6 9 6 23 74 26
1 15
34 12
26 24
25 12
43 6
12 34
2 18
18 4 4 1 26 68 46
33 6
8 16
45 2
42 1
9 23
43 6
11 20
34 1
23 2
14 2
23 19
21 10
8 6
43 7
21 29
6 2
17 1
30 12
20 5 3 6 14 24 41
5 36
31 12
2 35
4 15
44 1
2 9
5 39
19 2
28 5
25 21
3 28
7 18
1 31
17 9
7 4
4 30
36 7
17 24
1 20
16 3
11 2 3 9 89 39 11
30 2
8 41
13 9
20 9
18 9
23 20
26 11
14 33
8 35
12 35
9 26
7 3 4 10 47 79 87
2 24
1 41
8 1
9 5
24 2
30 1
7 29
7 7 8 8 56 80 39
7 26
35 5
16 28
14 29
16 32
21 18
3 26
12 8 2 9 17 72 28
8 29
4 1
17 24
40 2
21 8
6 9
5 13
17 9
5 39
4 31
28 4
3 36
7 1 8 5 98 57 61
1 4
30 1
27 13
7 11
10 16
21 14
33 9
6 10 5 2 62 3 32
5 21
15 31
10 29
11 15
26 8
5 15
14 12 5 16 145 173 246
29 6
19 28
18 31
33 12
14 30
29 19
33 11
11 16
14 33
6 38
44 5
16 20
18 22
4 38
23 20 6 20 480 471 199
24 23
10 9
9 29
39 6
19 27
24 8
23 12
15 18
23 19
27 8
27 16
14 11
46 3
13 36
4 39
18 19
40 10
16 8
20 28
5 19
26 7
27 13
12 36
21 11 8 12 167 294 326
31 7
19 11
47 3
2 1
4 17
16 12
13 30
14 17
3 44
10 22
24 4
35 8
26 22
19 7
6 30
23 7
32 12
36 8
13 21
24 1
33 7
23 8 3 4 204 177 128
22 14
18 10
7 24
8 21
4 25
14 31
9 34
10 36
6 6
24 18
19 3
39 10
32 3
23 20
20 10
21 20
16 30
20 26
22 17
24 10
14 13
2 10
39 10
15 8 19 11 94 352 337
33 6
8 37
26 3
5 7
29 15
23 2
15 20
26 14
12 23
6 6
25 3
35 13
36 4
15 27
21 1
12 2 16 11 102 320 452
35 14
7 32
3 19
21 26
11 21
24 2
15 10
32 6
38 7
4 31
6 8
10 33
13 2 15 6 194 80 243
13 14
16 2
18 22
13 13
43 6
4 35
30 19
12 17
5 11
7 7
28 18
11 30
4 25
19 5 6 14 138 401 439
45 3
5 5
29 19
23 13
2 7
13 7
11 10
19 1
3 15
37 8
6 11
16 11
19 6
11 32
4 44
10 12
17 13
19 12
6 29
14 2 6 17 201 14 43
18 11
28 13
14 15
12 4
16 9
12 22
4 29
4 15
1 38
24 16
26 17
19 9
31 9
5 21
14 6 11 20 115 187 321
23 24
3 27
12 9
28 18
35 12
6 5
7 5
16 32
1 5
21 11
11 38
36 3
11 23
26 17
29 22 25 1 881 884 274
21 20
23 12
12 16
4 8
6 28
29 8
24 4
1 45
30 12
20 18
29 21
12 36
12 9
15 5
14 15
2 1
30 11
4 27
2 4
31 16
9 17
10 17
45 3
17 14
29 13
17 16
37 2
39 6
30 12
23 13 23 12 498 643 634
8 2
24 1
14 23
2 46
4 46
3 43
7 4
2 13
46 4
2 26
10 20
21 27
9 25
1 25
22 15
10 4
10 25
11 16
5 41
13 12
32 3
35 14
8 31
22 8 21 11 467 961 900
6 23
21 6
36 3
29 6
11 30
17 28
36 14
40 4
24 21
7 37
1 46
2 44
17 12
28 3
34 3
14 18
28 19
11 28
29 10
9 11
1 11
38 4
26 7 20 19 787 304 842
12 7
3 34
27 3
2 48
21 26
7 11
23 22
11 38
24 5
1 41
14 1
4 24
15 21
31 17
5 25
32 12
2 24
12 26
39 5
13 12
36 8
11 9
10 1
6 12
25 11
19 16
34 11 20 16 459 207 689
22 7
23 24
4 34
14 23
23 26
5 21
1 34
13 20
24 11
3 4
10 18
7 28
5 27
16 29
1 24
33 5
16 29
20 11
14 35
11 37
8 3
7 14
41 5
23 3
15 25
29 8
32 3
5 30
6 17
12 31
5 29
44 5
29 20
14 4
31 12 13 22 237 822 823
33 16
25 3
9 34
13 34
25 16
1 45
14 17
15 25
46 4
16 17
10 8
20 4
31 6
33 17
1 31
30 12
7 7
10 5
24 6
13 28
5 3
15 25
2 34
18 9
39 11
7 41
2 46
7 36
23 6
6 36
7 35
33 2 8 25 625 390 641
20 2
18 20
7 1
36 1
30 15
31 13
9 11
43 1
19 24
13 35
8 37
16 9
21 8
19 10
19 14
30 2
6 10
3 19
3 38
30 4
12 21
12 36
22 27
1 2
22 6
41 6
3 20
3 2
16 32
37 3
23 7
4 33
9 15
25 20 4 7 119 439 977
26 1
7 4
21 27
3 16
5 14
15 26
34 10
3 29
15 24
5 13
3 28
33 17
30 13
20 10
20 13
16 28
14 7
1 4
41 3
4 23
30 6
16 30
10 30
19 27
5 39
22 7 2 23 435 733 788
37 2
25 7
15 28
31 5
24 1
32 4
36 5
35 12
31 9
1 23
17 18
32 10
30 14
22 2
1 9
19 23
21 2
31 17
17 31
8 30
41 5
18 27
22 7 12 9 393 913 905
1 16
37 9
21 20
15 13
18 21
5 38
11 14
27 13
14 35
26 17
8 28
19 10
24 12
9 40
5 10
21 1
11 34
19 15
10 30
22 19
24 23
1 23
33 8 32 7 942 106 497
49 1
15 4
6 28
22 19
27 6
10 40
33 5
23 11
20 18
28 15
21 4
5 6
9 15
39 7
21 16
5 34
3 21
28 5
36 1
22 18
17 6
6 16
26 2
39 3
8 19
9 30
12 24
3 9
19 19
36 12
10 1
19 7
28 21
48 1 4 36 965 152 460
27 11
4 26
2 45
23 15
5 26
11 26
2 9
12 29
7 19
13 21
20 8
28 12
12 31
40 2
19 11
18 14
34 8
20 9
32 2
17 33
28 3
36 9
14 35
4 19
3 27
8 7
11 33
10 14
18 22
11 21
11 5
6 36
10 25
26 6
24 24
35 8
15 9
29 12
17 1
11 13
1 6
7 20
16 22
31 8
17 19
34 12
15 25
3 3
43 13 22 9 688 476 169
16 21
11 13
44 5
21 12
26 7
16 24
6 30
36 2
14 32
2 48
9 20
27 5
30 9
11 27
26 13
33 12
7 28
26 19
16 30
3 7
5 17
21 4
2 28
25 21
2 2
11 4
2 48
26 21
9 30
12 2
9 30
4 23
10 19
13 32
26 23
24 14
15 5
4 28
17 11
31 4
4 13
5 17
10 10
37 14 4 15 463 441 250
10 14
36 12
18 28
3 27
7 36
16 16
11 12
24 22
36 6
31 5
9 40
6 10
28 11
43 1
40 5
11 27
25 8
29 3
14 31
2 4
12 23
24 24
33 10
19 11
38 10
32 11
24 10
16 30
42 5
22 16
20 16
3 3
1 5
30 8
8 39
10 22
1 26
31 17 4 4 979 652 689
32 17
26 13
34 16
8 34
24 21
4 12
6 26
4 26
28 8
26 19
7 41
36 8
26 11
32 15
8 9
9 14
37 9
36 5
32 3
27 14
27 3
2 48
8 28
7 25
28 11
26 6
39 9
23 8
39 6
5 40
27 8
50 16 23 2 947 875 329
1 41
35 6
3 28
12 15
28 20
22 21
23 22
35 2
23 15
32 12
10 31
18 8
1 25
22 1
44 6
26 17
18 17
14 21
16 2
17 6
26 20
17 21
45 3
11 31
31 9
21 10
6 23
48 2
10 36
14 29
1 11
34 15
44 3
17 16
9 15
28 17
35 11
7 4
17 30
2 18
38 8
21 24
1 13
4 28
18 24
17 21
25 14
7 3
48 2
36 9
50 22 8 8 756 883 690
16 11
8 30
45 3
42 6
26 22
7 39
4 27
19 7
14 20
48 2
15 8
9 1
3 15
16 4
1 6
39 10
15 28
27 2
34 11
26 14
33 14
2 7
15 27
5 27
19 8
17 5
11 24
2 44
9 41
7 39
8 14
3 3
34 11
16 32
35 14
12 13
12 19
7 20
36 12
15 27
3 22
1 22
19 4
5 14
37 8
43 1
9 31
2 21
12 29
16 7
50 21 18 2 471 299 613
8 10
19 20
20 11
39 11
46 4
30 17
13 27
19 6
16 24
29 1
25 14
37 8
25 3
22 27
18 22
15 10
10 7
25 12
36 11
14 4
27 22
7 27
33 3
8 24
5 27
24 14
33 4
7 41
16 26
37 9
26 8
18 15
14 36
21 4
34 4
5 44
19 20
18 23
10 40
12 14
10 15
42 3
25 21
31 11
18 14
12 9
2 3
17 10
10 1
26 4
50 9 2 19 627 406 191
7 33
14 32
13 19
2 28
2 8
16 34
6 12
5 16
6 4
43 7
2 35
6 16
28 10
40 7
39 6
1 43
27 7
18 23
12 33
23 4
16 30
29 11
7 35
18 1
14 5
42 2
18 25
13 27
31 11
19 1
2 2
31 14
1 36
23 15
9 34
10 35
48 2
7 18
12 27
22 22
20 15
7 2
13 1
10 3
4 45
15 24
1 36
17 5
14 23
39 5
50 2 6 6 223 60 491
39 3
27 12
21 2
39 5
2 1
12 2
35 9
15 12
6 33
6 18
2 16
9 40
15 15
6 23
8 1
16 6
29 18
14 12
10 11
2 41
3 13
6 11
12 11
15 6
22 21
44 5
14 17
14 15
1 11
6 25
6 43
17 7
12 27
5 40
18 19
15 30
22 5
4 34
1 14
19 30
23 5
4 31
28 13
28 4
5 30
6 23
27 20
5 10
2 33
10 29
/////////code
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_SIZE 1000000
#define INF 10000000
using namespace std;
int N, L1, L2, L3, P1, P2, P3;
int timeAdv[5];
int pointAdv[5];
int khach[100][2];
int adv[10] = {0};
int minTime, maxTime;
bool visited[101];
int result;
void reset(){
for(int i = 0; i < 100; ++i){
visited[i] = false;
}
}
int tinhDiem(){
int sum = 0;
for(int i = 0; i < N; ++i){
int point = 0;
for(int j = 0; j < 3; ++j){
if(khach[i][0] <= adv[j] && khach[i][0] + khach[i][1] >= adv[j] + timeAdv[j]){
if(point < pointAdv[j]){
point = pointAdv[j];
}
}
}
sum += point;
}
return sum;
}
void backtrack(int k){
if(k==3){
for(int i = 0; i < 3; ++i){
for(int j = 0; j < 3; ++j){
if(i != j){
if(timeAdv[i] + adv[i] > adv[j] && timeAdv[i] + adv[i] <= timeAdv[j] + adv[j])
{
return;
}
}
}
}
int n = tinhDiem();
if(n > result){
result = n;
}
return;
}
for(int i = 1; i <= 50; ++i){
adv[k] = i;
backtrack(k+1);
}
}
int main(){
//freopen("input.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; ++tc){
cin >> N;
for(int i = 0; i < 3; ++i){
cin >> timeAdv[i];
}
for(int i = 0; i < 3; ++i){
cin >> pointAdv[i];
}
minTime = INF;
maxTime = 0;
for(int i = 0; i < N; ++i){
cin >> khach[i][0] >> khach[i][1];
if(khach[i][0] < minTime){
minTime = khach[i][0];
}
if(khach[i][1] > maxTime){
maxTime = khach[i][1];
}
}
for(int i = 0; i < 5; ++i){
adv[i] = 0;
}
result = 0;
backtrack(0);
cout << "Case #" << tc << endl << result << endl;
}
return 0;
}Editor is loading...