- code:
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #define ls x<<1
- #define rs x<<1|1
- #define N 2105
- #define ll long long
- #define setIO(s) freopen(s".in","r",stdin)
- using namespace std;
- int n;
- ll ans;
- int tp[N],B[20],s[20];
- ll cost[N][12],f[N][N],C[N][2];
- int lca(int x,int y)
- {
- int i;
- for(i=n-1;i>=0;--i) if((x>>i)!=(y>>i)) break;
- return n-i-1;
- }
- void dfs(int x,int dep)
- {
- if(dep==n)
- {
- f[x][0]=C[x-B[n]][0];
- f[x][1]=C[x-B[n]][1];
- for(int i=0;i<dep;++i) f[x][s[i]^1]+=cost[x-B[n]][i];
- return;
- }
- s[dep]=0;
- memset(f[x],0x3f,sizeof(f[x][0])*(B[n-dep]+1));
- dfs(ls,dep+1),dfs(rs,dep+1);
- for(int i=0;i<=B[n-dep-1];++i) for(int j=0;i+j<=B[n-dep-1];++j)
- f[x][i+j]=min(f[x][i+j],f[ls][i]+f[rs][j]);
- s[dep]=1;
- dfs(ls,dep+1),dfs(rs,dep+1);
- for(int i=1;i<=B[n-dep-1];++i) for(int j=B[n-dep-1]+1-i;j<=B[n-dep-1];++j)
- f[x][i+j]=min(f[x][i+j],f[ls][i]+f[rs][j]);
- }
- int main()
- {
- // setIO("input");
- scanf("%d",&n);
- int i,j,v,a;
- for(i=0;i<=n;++i) B[i]=1<<i;
- for(i=0;i<B[n];++i) scanf("%d",&tp[i]);
- for(i=0;i<B[n];++i) C[i][tp[i]]=0,scanf("%d",&C[i][tp[i]^1]);
- for(i=0;i<B[n];++i) for(j=i+1;j<B[n];++j)
- {
- a=lca(i,j),scanf("%d",&v);
- cost[i][a]+=v,cost[j][a]+=v;
- }
- dfs(1,0);
- ans=1ll<<60;
- for(i=0;i<=B[n];++i) ans=min(ans,f[1][i]);
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3367747.html