Untitled

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

int N;

int quan[21];
int cost[21];

int linh[21];
int vslinh[21];
int k1 = 0;
int ars[12];

void reset()
{
	for(int i = 0; i < 21; i++)
	{
		quan[i] = 0;
		cost[i] = 0;
		linh[i] = 0;
		vslinh[i] = 3;
		ars[i]  = 0;
	}
}

void capnhat()
{
	for(int i = 0; i < k1; i++)
	{
		ars[i] = linh[i];
	}
	for(int i = 0; i < k1; i++)
	{
		vslinh[i]--;
	}
}

void khongcapnhat()
{
	for(int i = 0; i < k1; i++)
	{
		linh[i] = ars[i];
	}
	for(int i = 0; i < k1; i++)
	{
		vslinh[i]++;
	}
}


void Hugo(int chiphi,int binhsi, int k, int &min)
{

	if(k == N)
	{
		if(min > chiphi)
		{
			min = chiphi;
		}
		return;
	}
	if(chiphi > min)
	{
		return;
	}
	for(int i = 0; i < 3; i++)
	{
		if(i == 0)
		{
			// chon tra tien de qua cua
			Hugo(chiphi + cost[k], binhsi, k + 1, min);
		}
		else if( i == 1)
		{
			// chon tra gap doi de mua binh si
			linh[k1] = quan[k];
			k1++;
			Hugo(chiphi + 2 * cost[k], binhsi + quan[k], k + 1, min);
			linh[k1] = 0;
			k1--;
		}
		else
		{
			// chon chien dau
			if(binhsi >= quan[k])
			{
				// cap nhat tat ca binh si da chien dau mot lan va nhung ai chet va loai
				capnhat();
				int t = quan[k];
				for(int i = 0; i < k1; i++)
				{
					if(vslinh[i] >= 0 && linh[i] > 0)
					{
						if(linh[i] >= quan[k])
						{
							linh[i] = linh[i] - quan[k];
							break;
						}
						else
						{
							quan[k] = quan[k] - linh[i];
							linh[i] = 0;
						}
					}
				}
				Hugo(chiphi, binhsi - t, k + 1, min);
				quan[k] = t;
				khongcapnhat();
			}
		}
	}
}

int main()
{
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		k1 = 0;
		reset();
		cin >> N;
		for(int i = 0; i < N; i++)
		{
			cin >> quan[i];  // soluong linh o moi cong
			cin >> cost[i]; // chi phi o moi cong
		}
		// so quan cua hugo ban dau la 0
		int min = 100000;
		Hugo(0, 0, 0, min);
		cout<<"#"<<tc<<" "<<min<<endl;
	}
}