Untitled
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
#include <iostream> using namespace std; int N; int qc[4];// do dai cua quang cao int sc[4];// diem so int A[51]; // thoi gian khach hang bat dau den int D[51]; // khoang thoi gian khach hang o lai int tim[4][2]; // quang cao thi k co time bat dai time[k][0] va thoi gian kt time[k][1] void reset() { for(int i = 0; i < 4; i++) { for(int j = 0; j < 2; j++) { tim[i][j] = 0; } } } // tinh diem so xem quang cao khi da xem du 3 quang cao int scc() { int diem[51] = {0}; //diem so khack hang nhan duoc for(int i = 1; i <= N; i++) { for(int j = 1; j <= 3; j++) { int xbgin = tim[j][0]; int xend = tim[j][1]; if(A[i] <= xbgin && A[i] + D[i] >= xend) { if(diem[i] < sc[j]) { diem[i] = sc[j]; } } } } int sum = 0; for(int i = 1; i <= N; i++) { sum = sum + diem[i]; } return sum; } // kiem tra xem quang cao thu k duoc dat vao vi tri i co bi trung hay khong bool check(int k, int bgin) { int end = bgin + qc[k]; for(int i = 1; i <= 3; i++) { if(tim[i][0] != 0 && tim[i][1] != 0 && i != k) { // time1 la time bat dau time2 la kt if(bgin <= tim[i][0] && tim[i][1] < end) { return false; } if(tim[i][0] <= bgin && bgin <= tim[i][1] && tim[i][1] < end) { return false; } if(bgin <= tim[i][0] && tim[i][0] < end && end < tim[i][1]) { return false; } if(tim[i][0] <= bgin && end < tim[i][1]) { return false; } } } return true; } void quangcao(int &max, int k) { if(k == 4) { int t = scc(); if(max < t) { max = t; } return; } // chon thoi diem chieu cua quang cao for(int i = 1; i <= 50; i++) { if(check(k, i) == true) { tim[k][0] = i; tim[k][1] = i + qc[k]; quangcao(max, k + 1); tim[k][0] = 0; tim[k][1] = 0; } } } int main() { freopen("input.txt", "r", stdin); int testcase; cin >> testcase; for(int tc = 1; tc <= testcase; tc++) { cin >> N; for(int i = 0; i < 51; i++) { A[i] = 0; D[i] = 0; } reset(); for(int i = 1; i <= 3; i++) { cin >> qc[i]; // do dai cua quang cao thu i } for(int i = 1; i <= 3; i++) { cin >> sc[i]; // diem so cua quang cao thu i } // thoi gian den va di for(int i = 1; i <= N; i++) { cin >> A[i]; cin >> D[i]; } int max = 0; quangcao(max, 1); cout<<"Case #"<<tc<<endl<<max<<endl; } }
Editor is loading...