Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
0
Indexable
Never
#include<iostream>
using namespace std;

int N;

int enemy[25]; // quan dich
int price[25]; // cai gia phai tra

int minPay; // so tien nho nhat phai tra

void go(int k,int b0, int b1, int b2, int sumPay)
{
	if(k == N)
	{
		minPay = min(minPay, sumPay);
		return;
	}
	if(sumPay > minPay)	return;

	for(int i = 0; i < 3; i++)
	{
		if(i == 0)	// TH pass
		{
			go(k + 1,b0,b1,b2,sumPay + price[k]);
		}
		if(i == 1) // TH hire
		{
			go(k + 1,b0 + enemy[k],b1,b2, sumPay + 2*price[k]);
		}
		if(i == 2) // TH battle
		{
			if(b0 + b1 + b2 >= enemy[k])
			{
				if(b2 >= enemy[k])
				{
					go(k+1,0,b0,b1,sumPay);
				}
				else if(b1 + b2 >= enemy[k])
				{
					go(k+1,0,b0, b1 + b2 - enemy[k], sumPay);
				}
				else if(b0 + b1 + b2 >= enemy[k])
				{
					go(k+1, 0, b0 + b1 + b2 - enemy[k],0,sumPay);
				}
			}
		}
	}
}

int main()
{
	freopen("Text.txt","r",stdin);

	int T;
	cin>>T;
	for(int tc = 1; tc <= T; tc++)
	{
		cin>>N;
		for(int i = 0; i< N; i++)
		{
			cin>>enemy[i]>>price[i];
		}
		minPay = 10000000;
		go(0,0,0,0,0);
		cout<<"#"<<tc<<" "<<minPay<<endl;
	}
	return 0;
}