# Untitled

unknown
plain_text
20 days ago
1.5 kB
1
Indexable
Never
```#include <iostream>
#define MAX_N 20
#define MAX_SOLDIERS 1000
#define INF 1000000000

using namespace std;

struct Gate {
int soldiers;
int cost;
};

int T, N;
Gate gates[MAX_N];
int dp[MAX_N][MAX_N * MAX_SOLDIERS / 2 + 1];

int min(int a, int b) {
return (a < b) ? a : b;
}

int main() {
cin >> T;

for (int t = 0; t < T; t++) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> gates[i].soldiers >> gates[i].cost;
}

for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N * MAX_SOLDIERS / 2; j++) {
dp[i][j] = INF;
}
}

dp[0][0] = 0;

for (int i = 0; i < N; i++) {
for (int j = 0; j <= N * MAX_SOLDIERS / 2; j++) {
if (dp[i][j] == INF) continue;

// Cách 1: Pass
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + gates[i].cost);

// Cách 2: Hire
dp[i + 1][j + gates[i].soldiers] = min(dp[i + 1][j + gates[i].soldiers], dp[i][j] + 2 * gates[i].cost);

// Cách 3: Battle
if (j >= gates[i].soldiers) {
dp[i + 1][j - gates[i].soldiers] = min(dp[i + 1][j - gates[i].soldiers], dp[i][j]);
}
}
}

int result = INF;
for (int j = 0; j <= N * MAX_SOLDIERS / 2; j++) {
result = min(result, dp[N][j]);
}

cout << "#" << t + 1 << " " << result << endl;
}

return 0;
}
```