Untitled
unknown
plain_text
2 years ago
6.5 kB
8
Indexable
A shop need to display the advertisement 3 times a day.
However, they only has 1 electric board to display the advertisement, hence they should select the time to display advertisements so that visitors can watch them as much as possible.
When visitors watch advertisement, they can get points which calculated as below :
1. Three Ads have length L1, L2, L3 and the points a person can get after watched them P1, P2, P3.
2. A visitor can get the point of a Ads only when he/she watch the Ads fully (from beginning to the end of that Ads )
3. When a visitor watch more than one Ads and also get the point for them, only the Ads with highest point will be given to that person.
4. Only one Ads can be displayed on electric board at a time (But the next Ads can be displayed right after the previous one ended)
Given the length of each Ads L1, L2, L3 and the point gained for them P1, P2, P3, the arrival time of each visitor into the shop and the time duration that he/she stay in the shop, write a program to select advertisement display time so that as many points as possible can be given to visitors. Print out the total sum of points that the visitors can get.
Ex: There are 7 visitors go to the shop with the arrival time and staying duration as below
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Arrival Time
2
6
3
7
1
2
1
Time Duration
2
4
3
2
1
1
10
Length
Point(s)
Advertisement 1
1
1
Advertisement 2
2
2
Advertisement 3
3
3
Assuming that Ads1 is displayed at time 2, Ads2 at time 7 and Ad3 at time 3, the visitors will watched the ads as below schedule :
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Ads 1
Watch
-
-
-
-
Watch
Watch
Ads 2
-
Watch
-
Watch
-
-
Watch
Ads 3
-
-
Watch
-
-
-
Watch
(Note that visitor 1 didn't watch Ads3 fully, so the point of Ads3 is not given to him)
The points that each visitor can get from watching Ads is show as below :
Visitor 1
Visitor 2
Visitor 3
Visitor 4
Visitor 5
Visitor 6
Visitor 7
Ads 1
1
-
-
-
-
1
1
Ads 2
-
2
-
2
-
-
2
Ads 3
-
-
3
-
-
-
3
Total 12 Points
1
2
3
2
0
1
3
(Visitor 7 watched all Ads fully, however he can only get the highest of one Ads - which is 3 points of Ads 3)
There are many way to arrange the display time, and the method above give us the maximum sum of points which visitors can get, so the answer in this case is 12.
[Constraints]
- The number of visitors N (1 ≤ N ≤ 50)
- The arrival time Ai, the time duration Di of each visitor and the length of each Ads L1, L2, L3 are given as integers (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)
- Ai + Di ≤ 50
- L1 + L2 + L3 ≤ 50
- The starting time of an Ads : 1 ≤ starting time ≤ 50
- P1, P2, P4 are integers (1 ≤ P1, P2, P3 ≤ 1000)
[Input]
The 1st line given T - the total number of TC (T ≤ 50)
In each TC :
- The 1st line contains N, L1, L2, L3, P1, P2, P3 in this order
- The next N lines : each line gives the arrival time Ai and time duration Di of each visitor
[Output]
5 // Number of test cases 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
Out put the maximum sum of points that visitors can get from watching advertisements.
Case #1
12
Case #2
18
Case #3
17
Case #4
16
Case #5
17998
Code:
#include<iostream>
using namespace std;
int N;
int tgian[50][2];
int ads[2][3]; // luu do dai ads va diem cua tung ads
int kq, min_time, max_time;
int plan[2][3]; // luu ke hoach mo cac ads, hang dau la start time, hang sau la end time
void reset_plan(){
for(int i = 0; i < 3; i++){
plan[0][i] = plan[1][i] = 0;
}
}
bool check(int start, int end){ //check tgian dang muon dat ads xem co bi trung voi cac ads khac ko
for(int i = 0; i < 3; i++){
if(start> plan[0][i] && start < plan[1][i]) return false;
if(end > plan[0][i] && end < plan[1][i]) return false;
if(plan[0][i] > start && plan[0][i] < end) return false;
if(plan[1][i] > start && plan[1][i] < end) return false;
}
return true;
}
void set(int start, int end, int i){
plan[0][i] = start;
plan[1][i] = end;
}
void unset( int i){
plan[0][i] = 0;
plan[1][i] = 0;
}
int tinh_tong(){
int sum = 0;
for(int i = 0; i < N; i++){
int max_point = 0;
for(int j = 0; j < 3; j++){
if(tgian[i][0] <= plan[0][j] && tgian[i][0] + tgian[i][1] >= plan[1][j]) { // xem thoa man tgian ko
if(ads[1][j] > max_point) max_point = ads[1][j];
}
}
sum += max_point;
}
return sum;
}
void backtrack(int i){ //backtrack tung ads
if(i ==3){
int tong = tinh_tong();
if(tong > kq) kq =tong;
return;
}
for(int h = min_time; h <= 50; h++){ // check tung khoang tgian co the bat dau cua tung ads tu min_time den 50
if(check(h, h + ads[0][i])){ //check xem ads day co the dat trong tgian tu h den h + ads[0][i] khong, de ko bi trung voi cac quang cao khac da dat
set(h,h+ads[0][i],i); // neu co the thi dat tgian bat dau la h, tgian ket thuc la h + ads[0][i]
backtrack(i+1);
unset(i);
}
}
}
int main(){
//freopen("Text.txt", "r", stdin);
int test;
cin>> test;
for(int tc = 1; tc <= test; tc++){
cin >> N ;
for(int i = 0; i < 3; i++){
cin >> ads[0][i]; //do dai
}
for(int i = 0; i < 3; i++){
cin >> ads[1][i]; // diem
}
for (int i = 0; i< N ; i++){
cin >> tgian[i][0] >> tgian[i][1]; // dau tien la tgian vao, sau la tgian luu tru
}
min_time = 100000;
max_time = 0;
for(int i = 0; i < N; i++){ // tim tgian vao som nhat va tgian ra muon nhat cua tat ca cac khach
if(tgian[i][0] < min_time) min_time = tgian[i][0];
if( tgian[i][0] + tgian[i][1] > max_time) max_time = tgian[i][0] + tgian[i][1] ;
}
kq = 0;
reset_plan();
backtrack(0);
cout << "Case #"<< tc << endl;
cout << kq<<endl;
}
return 0;
}
Editor is loading...