KSPREE - Triple Shoot
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
const int INF=(int)1e9+7;
int n;
int a[23];
int f[(1<<20)+7];
int s[(1<<20)+7];
int lg2[(1<<20)+7];
int bit(int x,int i) {
return ((x|(1<<i))==x);
}
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
void process(void) {
scanf("%d",&n);
REP(i,n) scanf("%d",&a[i]);
REP(i,n) lg2[1<<i]=i;
REP(i,1<<n) if (i>0) {
int t=lg2[i&(-i)];
s[i]=s[i^(1<<t)]+a[t];
}
memset(f,0x3f,sizeof f);
f[(1<<n)-1]=0;
FORD(i,(1<<n)-1,1) if (f[i]<INF)
REP(j,n) {
int pr=(j-1+n)%n;
int ne=(j+1+n)%n;
int ns=((1<<n)-1)^(1<<pr)^(1<<j)^(1<<ne);
minimize(f[i&ns],f[i]+s[i&ns]);
}
printf("%d",f[0]);
}
int main(void) {
process();
return 0;
}