KSPREE - Triple Shoot
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 20
#define on(num, bit) ((num & 1 << (bit)) != 0)
inline int toff(int num, int b1, int b2, int b3) {
return num & ~(1 << (b1)) & ~(1 << (b2)) & ~(1 << (b3));
}
int a[20], n;
int f[1 << 20];
int backtrack(int mask, int sum) {
int &res = f[mask];
if(res != -1) return res;
res = INT_MAX;
for(int i = 0; i < n; ++i) if(on(mask, i)) {
int minus = 0;
for(int j = -1; j <= 1; ++j) if(on(mask, (i+j+n)%n)) minus += a[(i+j+n)%n];
res = min(res, backtrack(toff(mask, (i-1+n)%n, i, (i+1)%n), sum - minus) + sum - minus);
}
return res;
}
int main() {
int sum = 0;
scanf("%d", &n); for(int i = 0; i < n; ++i) { scanf("%d", a+i); sum += a[i]; }
memset(f, -1, sizeof f); f[0] = 0;
printf("%d\n", backtrack((1 << n) - 1, sum));
return 0;
}