Untitled

 avatar
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...