[NOI2006] 网络收费解题报告

comcopy · 2023-09-13 16:38:58 · 个人记录

收获颇丰。

考虑一个点对 (i,j) 对于他们 lca 的贡献。

挑出其中一个点 i ，发现其贡献当前仅当点 i 与 lca 子树内的个数较小的付费方案颜色相同，会产生 f_{i,j} 的贡献，j 同理。

将所有非叶子结点按其个数较少的颜色染色。

发现对于一个点 i ，其对其的祖先有贡献当且仅当该祖先与该点颜色相同。

所以我们考虑把 (i,j) 拆成两条链，变成 (i,lca) 与 (lca,j) 并在这两条路径上垒值，这样可以在枚举 lca 的同时直接计算贡献而不用枚举 j 。

拆点是第一个思维点。

很显然我们将问题转换为了树链上的问题。

接下来就是考虑如何枚举点 i 的祖先的状态。

发现题目中的 n 等价于我们建出来的树的深度。刚开始的思路状压瞬间复活并跳出来给了你几个巴掌，告诉你：它是有用的。

没错，我们通过状压记录祖先的状态，并开始 dp 。

dp?刚刚好像没提到啊？没事现在提到了。

考虑这么一个状态：

表示点 u ，其子树内叶子结点为 1 的个数为 j 且祖先状态为 st 的最小代价。

显然得到以下转移式子：

对于单点其对祖先的贡献依据颜色来累加，详情看代码。

考虑空间不够，而非叶子结点 dp 没有记录的必要，将状态直接放到函数里传递。

#include<bits/stdc++.h>
using namespace std;
inline bool _u(char x){return x>='0'&&x<='9';}
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
    for(;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
    return x*f;
}
inline void write(int num,bool flag=0){
    static int st[39],tp=0;
    num<0&&(putchar('-'),num=-num);
    do st[++tp]=num%10;while(num/=10);
    while(tp) putchar(st[tp--]|48);
    putchar(flag?'\n':' ');
    return;
}
const int N=(1<<11)+10;
int fy[N][N],a[N],c[N],tag[N];
int dp[N][N];
#define ls (now<<1)
#define rs (now<<1|1)
inline void dfs(int l,int r,int now,int st,int dep){
    if(l==r){
        dp[now][0]=a[l]*c[l],dp[now][1]=c[l]*(!a[l]);
        for(int i=0,j=now>>1;i<dep;++i,j>>=1)
            dp[now][!((st>>i)&1)]+=fy[now][j];
        return;
    }
    int mid(((r-l)>>1)+l),sum=r-l+1;
    dfs(l,mid,ls,st<<1,dep+1),dfs(mid+1,r,rs,st<<1,dep+1);
    for(int i=0;i<=sum/2;++i){
        dp[now][i]=1e9;
        for(int j=0;j<=i;++j)
            dp[now][i]=min(dp[now][i],dp[ls][j]+dp[rs][i-j]);
    }
    dfs(l,mid,ls,st<<1|1,dep+1),dfs(mid+1,r,rs,st<<1|1,dep+1);
    for(int i=sum/2+1;i<=sum;++i){
        dp[now][i]=1e9;
        for(int j=0;j<=sum/2;++j)
            if(i-j<=sum/2) dp[now][i]=min(dp[now][i],dp[ls][j]+dp[rs][i-j]);
    }
    return;
}
inline int lca(int u,int v){
    for(;u!=v;u>>=1,v>>=1);
    return u; 
}
int ans=1e9;
inline void slove(int n){
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) c[i]=read();
    for(int i=n;i<n*2;++i)
        for(int j=i+1,x;j<n*2;++j)
            x=read(),fy[i][lca(i,j)]+=x,fy[j][lca(i,j)]+=x; 
    dfs(1,n,1,0,0);
    for(int i=0;i<n;++i) ans=min(ans,dp[1][i]);
    return write(ans,1);
}

int n;
signed main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    n=read();
    slove(1<<n);
    return(0-0);
}