Untitled

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

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

int linh1 = 0, linh2 = 0, linh3 = 0;

void Hugo(int chiphi, int k, int &min)
{
	if(k == N)
	{
		if(min > chiphi)
		{
			min = chiphi;
		}
		return;
	}
	if(chiphi > min)
	{
		return;
	}
	for(int i = 0; i <= 2; i++)
	{
		if(i == 0)
		{
			// chon tra ve qua cong
			Hugo(chiphi + cost[k], k + 1,min);
		}
		else if( i == 1)
		{
			linh1 = linh1 + quan[k];
			Hugo(chiphi + 2 * cost[k], k + 1, min);
			linh1 = linh1 - quan[k];
		}
		else
		{
			if(linh1 + linh2 + linh3 >= quan[k])
			{
				int t1 = linh1, t2 = linh2, t3 = linh3;
				int t = quan[k];
				if(linh3 > 0)
				{
					if(linh3 >= t)
					{
						linh3 = linh3 - t;
						t = 0;
					}
					else
					{
						t = t - linh3;
						linh3 = 0;
					}
				}
				if(t > 0 && linh2 > 0)
				{
					if(linh2 >= t)
					{
						linh2 = linh2 -t;
						t = 0;
					}
					else
					{
						t = t - linh2;
						linh2 = 0;
					}
				}
				if(t > 0 && linh1 > 0)
				{
					if(linh1 >= t)
					{
						linh1 = linh1 - t;
						t = 0;
					}
					else
					{
						t = t - linh1;
						linh1 = 0;
					}
				}
				// cap nhat lai linh
				linh3 = linh2, linh2 = linh1, linh1 = 0;
				Hugo(chiphi, k + 1, min);
				linh1 = t1;
				linh2 = t2;
				linh3 = t3;
			}
		}
	}
}


int main()
{
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		cin >> N;
		linh1 = linh2 = linh3 = 0;
		for(int i = 0; i < N; i++)
		{
			cin >> quan[i];
			cin >> cost[i];
		}

		int min = 100000;
		Hugo(0, 0, min);
		cout<<"#"<<tc<<" "<<min<<endl;
	}
}