Hướng dẫn giải của Educational Backtracking: Đổi dấu
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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;
}
Bình luận