KSPREE - Triple Shoot
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
#define max 1000000
int main()
{
// freopen("KSPREE.in","r",stdin);
int n,a[44],mu2[21],b[20],f[150001];
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = n+1;i<=2*n;i++) a[i] = a[i-n];
int KQ = max;
mu2[0] = 1;
for(int i = 1;i<=20;i++)
mu2[i] = mu2[i-1]*2;
for(int ii = 1;ii<=n;ii++)
{
// printf("?\n");
int tong = 0,R,x[20],t;
for(int i = ii;i<ii+n-3;i++)
{
b[i-ii] = a[i];
tong = tong + a[i];
}
// printf("%d\n ",tong);
int m = n-3;
f[0] = 0;
for(int i = 1; i <= mu2[m]-1;i++)
{
f[i] = max;
R = i,t = 0;
for(int j = 0;j<m;j++)
{
x[j] = R%2;
R = R/2;
t = t+x[j]*b[j];
// printf("%d ",t);
}
for(int j = 0;j<=m-3;j++)
{
if(x[j]!=0 ||x[j+1]!=0 || x[j+2]!=0)
if(f[i]>f[i-mu2[j]*x[j]-mu2[j+1]*x[j+1]-mu2[j+2]*x[j+2]]+t-b[j]*x[j]-b[j+1]*x[j+1]-b[j+2]*x[j+2])
f[i]=f[i-mu2[j]*x[j]-mu2[j+1]*x[j+1]-mu2[j+2]*x[j+2]]+t-b[j]*x[j]-b[j+1]*x[j+1]-b[j+2]*x[j+2];
}
if(f[i] == max ) f[i] = 0;
// printf("%d %d\n",i,f[i]);
}
if(f[mu2[m]-1]+tong<KQ)
KQ = f[mu2[m]-1]+tong;
}
printf("%d",KQ);
// getch();
}