Editorial for Educational Backtracking: Đổi dấu
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta có thể sử dụng thuật toán duyệt trâu. Giả sử biết giá trị của ~s_1~ đến ~s_i~, ta có thể thử từng giá trị của ~s_{i+1}~, sau đó đệ quy để thử tiếp.
Code C++:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 17;
int n;
int h[maxn];
int w[maxn][maxn];
int state[maxn];
int sum;
int ans;
void brute(int p) {
if (p == n) {
ans = min(ans, sum);
} else {
for (int s: {-1, 1}) {
state[p] = s;
sum += s * h[p];
for(int j = 0; j < p; j++) sum += state[j] * s * w[j][p];
brute(p + 1);
sum -= s * h[p];
}
}
}
signed main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> h[i];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) cin >> w[i][j];
}
ans = INT_MAX / 2;
brute(0);
cout << ans << endl;
}
Nhận xét: mỗi khả năng trong ~2^n~ tập giá trị có thể của ~s_1, s_2, ..., s_n~ có thể được biểu diễn bằng một số nguyên không âm ~v (0 \leq v < 2^n)~. Giá trị của ~s_1~ là -1 chi khi bit nhỏ nhất của ~v~ là 0; ~s_2~ = -1 chỉ khi bit nhỏ thứ 2 của ~v~ là 0; vv. Như vậy ta có thể duyệt qua toàn bộ ~2^n~ khả năng bằng cách duyệt qua các số nguyên dương tương ứng từ 0 đến ~2^n - 1~.
Code C++:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 20;
const int inf = LLONG_MAX / 100;
int n;
int h[maxn];
int w[maxn][maxn];
signed main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> h[i];
for (int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) cin >> w[i][j];
int ans = inf;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
int bit_i = mask >> i & 1;
sum += (bit_i * 2 - 1) * h[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int bit_i = mask >> i & 1;
int bit_j = mask >> j & 1;
sum += (bit_i * 2 - 1) * (bit_j * 2 - 1) * w[i][j];
}
}
ans = min(ans, sum);
}
cout << ans << endl;
}
Comments