[NOI2006] 網路收費

賊有意思的一道題。考慮把費用給轉化一下，觀察

如果定義葉節點的狀態 {{A,0},{B,1}}，非葉節點的狀態 {{nA>=nB,0},{nA<nB,1}}，結合上圖可以得出

• 葉節點x,y(x<y)的狀態相同
  • 葉節點狀態與lca(x,y)狀態相同，費用0
  • 葉節點狀態與lca(x,y)狀態不同，費用2f[x,y]
• 葉節點x,y(x<y)的狀態不同，費用f[x,y]

技巧化的，直接定義葉節點x關於祖先d的權值為h(x,d)=[x的狀態≠d的狀態]Σf[x,y]，其中y是d子樹管轄的不等於x的葉節點。

這樣一來，如果實現清楚了祖先的狀態，x的貢獻就等於Σh(x,d)了。

於是考慮枚舉祖先的狀態併進行dp，設f[x,i]表示在x子樹中出現了i個0狀態葉節點的最小代價，轉移部分比較簡單，參考代碼就行。

沒講太清楚明天補補吧。千萬記得初始化dp數組！！！

update：已經很詳盡了還有什麼要不補的啊喂，滾去睡覺了233

#include <bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;

int n;
int cv[2050],ori[2050],tmp[2050];
int dp[2050][2050],v[2050][2050];
int lq[12],rq[12];

void dfs(int x,int l,int r,int set,int dep) {
    memset(dp[x],inf,sizeof dp[x]);
    if(l==r) {
        dep--;
        dp[x][0]=ori[l]?0:cv[l];
        dp[x][1]=ori[l]?cv[l]:0;
        for(int i=1; i<=dep; ++i) {
            int mid=(lq[i]+rq[i])>>1;
            int key=!(1&(set>>(dep-i))); //相異有貢獻
            if(l<=mid) dp[x][key]+=v[l][rq[i]]-v[l][mid];
            else dp[x][key]+=v[l][mid]-v[l][lq[i]-1];
        }
        return;
    }
    int mid=(l+r)>>1,len=r-l+1;
    lq[dep]=l,rq[dep]=r;

    dfs(ls,l,mid,set<<1,dep+1);
    dfs(rs,mid+1,r,set<<1,dep+1);

    for(int i=0; i<len/2; ++i)
    for(int j=0; j<=i; ++j) 
        dp[x][i]=min(dp[x][i],dp[ls][j]+dp[rs][i-j]);

    dfs(ls,l,mid,set<<1|1,dep+1);
    dfs(rs,mid+1,r,set<<1|1,dep+1);
    for(int i=len/2; i<=len; ++i)
    for(int j=0; j<=i; ++j) 
        dp[x][i]=min(dp[x][i],dp[ls][j]+dp[rs][i-j]);
}

int main() {
    scanf("%d",&n); n=1<<n;
    for(int i=1; i<=n; ++i) scanf("%d",ori+i);
    for(int i=1; i<=n; ++i) scanf("%d",cv+i);
    for(int i=1; i<=n; ++i) 
    for(int j=i+1; j<=n; ++j) {
        scanf("%d",&v[i][j]);
        v[j][i]=v[i][j];
    }
    for(int i=1; i<=n; ++i) 
    for(int j=1; j<=n; ++j) 
        v[i][j]+=v[i][j-1];
    dfs(1,1,n,0,1);
    int ans=inf;
    for(int i=0; i<=n; ++i) 
        ans=min(ans,dp[1][i]);
    printf("%d\n",ans);
    return 0;
}