hugo_venhac

duyvan
plain_text
16 days ago
2.9 kB
12
Indexable
Never
```//hugo_venha_oanhnhau
#include<iostream>
#define endl '\n'
using namespace std;

int N, ans;
int creeps[7][3];
int price_gate[7];

void copy_arr(int arr1[7][3], int arr2[7][3])
{
for(int i = 0; i < N; ++i)
for(int j = 0; j < 3; ++j)
arr2[i][j] = arr1[i][j];
}

void backtrack(int x, int crs, int score)
{
if(score >= ans)	return;
if(x == N)
{
if(score < ans)
ans = min(ans, score);
return;
}
for(int i = 1; i <= 3; ++i)
{
if(i == 1)	backtrack(x + 1, crs, score + price_gate[x]);	//Neu qua cong do, nap tien vao cong -> score tang, crs khong doi, x them 1 cong
if(i == 2)
{
creeps[x][1] = creeps[x][0];	//Nap linh vao quan minh
backtrack(x + 1, crs + creeps[x][0], score + price_gate[x]*2); //Neu mua linh, score cong them gap 2, linh cong do them, tong crs them linh
creeps[x][1] = 0;	//Quay lui, creeps cua cong do ve lai 0
}
if(i == 3 && crs >= creeps[x][0])
{
int copy_crs[7][3];
copy_arr(creeps, copy_crs);	//copy mang creeps truoc khi backtrack de ty quay lui
int enemy =  creeps[x][0];	//Dat bien so linh quan dich = linh cong do

for(int j = 0; j < N; ++j)	//Buoc 1: Cho moi tk quan cong do len 1 lan danh
if(creeps[j][1] > 0)
creeps[j][2]++;	//So lan danh cua cong do tang 1 lan

for(int j = 0; j < N; ++j)	//Buoc 2: Scan linh de danh
{
if(creeps[j][1] > 0)	//Neu cong do minh co mua linh
{
if(creeps[j][1] > enemy)	//Neu so quan lon hon dich -> linh giam theo so luong dich, dich = 0
{
creeps[j][1] -= enemy;
enemy = 0;
}
if(creeps[j][1] <= enemy) //Neu so quan nho hon hoac bang dich -> linh, so lan danh = 0, dich giam theo so luong quan
{
enemy -= creeps[j][1];
creeps[j][2] = 0;
creeps[j][1] = 0;
}
if(enemy == 0)	break;	//Neu so linh dich da het, break khoi tim quan dong minh nx
}
}

for(int j = 0; j < N; ++j)	//Buoc 3: Kiem tra xem co cong nao danh 3 lan chua, neu danh 3 lan -> cho giai tan
if(creeps[j][2] == 3)
{
creeps[j][2] = 0;
creeps[j][1] = 0;
}
crs = 0;	//reset creeps de cong lai tong quan linh sau tran chien
for(int j = 0; j < N; ++j)
if(creeps[j][1] > 0)	//Neu cong do con quan ta -> cong vao crs
crs += creeps[j][1];

backtrack(x + 1, crs, score);

copy_arr(copy_crs, creeps);
crs = 0;	//Sau backtrack, reset crs, copy lai mang arr cu, cong lai crs va quay lui tiep
for(int j = 0; j < N; ++j)
if(creeps[j][1] > 0)	//Neu cong do con quan ta -> cong vao crs
crs += creeps[j][1];
}
}
}

int main()
{
ios::sync_with_stdio(false);
freopen("inp.txt","r",stdin);
freopen("out.txt","w",stdout);
cin.tie(0);

ans = 0;
cin >> N;
for(int i = 0; i < N; ++i)
{
cin >> creeps[i][0] >> price_gate[i];
ans += price_gate[i];
}

backtrack(0,0,0);

cout << ans << endl;
return 0;
}```