【bzoj1495】[NOI2006]网络收费

2015.06.24 12:59 Wed | 62次阅读 | 旧日oi | 固定链接 | 源码

题目大意

自己看吧,注意题里的2N都是2^N……

题解

这是一类动态规划问题,当前决策会影响到未来决策,具体可以看那篇徐源盛的论文。
首先我们可以把收费情况分配到每个人身上,对于一个节点u,若其为a,则对每一边的选择b的节点算入sum[i][j]的费用,sum[i][j]是sum(f[i][k]),k为所有使得lca(i,k)==u的点,若其为b也是同理。这个可以预处理出来。
然后进行树形dp,用dp[u][j][k]表示节点u,u的子树中有k个选了a,u的父亲的状态为k(二进制)时的最小花费。然而这会MLE,我们发现j和k加起来最多只有12位,所以可以压缩到一起。
转移:dp[u][i][j]=min(dp[u<<1][k][j<<1|tmp]+dp[u<<1|1][i-k][j<<1|tmp]) ,tmp是当前点的状态。
看不懂的地方可以给我留言。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int dp[1<<11][(1<<12)+1],sum[1<<11][1<<11];
int n,cost[1<<11];
bool way[1<<11];
short f[1<<11][1<<11];
void tree_dp(int u,int son_num,int fa)
{
    if(!son_num)
    {
        for(int sum1,sum2,i=0;i<(1<<n);i++)
        {
            sum1=sum2=0;
            for(int j=0;j<n;j++)
                if(i&(1<<j)) sum1+=sum[u][j];
                else sum2+=sum[u][j];
            dp[u][i<<2]=sum1;dp[u][i<<2|1]=sum2;
            dp[u][(i<<2)+way[u]^1]+=cost[u];
        }
        return;
    }
    tree_dp(u<<1,son_num-1,fa<<1);
    tree_dp(u<<1|1,son_num-1,fa<<1);
    int st,st1,st2,now,i,j,k;
    for(i=0;i<=(1<<son_num);i++)
    {
        now=(i>(1<<son_num-1));
        for(j=max(0,i-(1<<son_num-1));j<=min(i,1<<son_num-1);j++)
        for(k=0;k<fa;k++)
        {
            st=i+((k<<1|now)<<(son_num+1));
            st1=j+((k<<1|now)<<(son_num+1));
            if(son_num>1&&j>(1<<son_num-2)) st1+=(1<<son_num);
            st2=(i-j)+((k<<1|now)<<(son_num+1));
            if(son_num>1&&(i-j)>(1<<son_num-2)) st2+=(1<<son_num);
            dp[u][st]=min(dp[u][st],dp[u<<1][st1]+dp[u<<1|1][st2]);
        }
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=(1<<n);i<(1<<n+1);i++) scanf("%d",&way[i]);
    for(int i=(1<<n);i<(1<<n+1);i++) scanf("%d",&cost[i]);
    for(int i=(1<<n);i<(1<<n+1)-1;i++)
        for(int j=i+1;j<(1<<n+1);j++)
            scanf("%d",&f[i][j]),f[j][i]=f[i][j];
    memset(dp,0x3f,sizeof(dp));
    for(int i=(1<<n);i<(1<<n+1);i++)
    {
        int len=1,st=i;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                for(int k=st-len;k<st;k++) sum[i][j]+=f[i][k];
                st-=len;
            }
            else for(int k=st+len;k<st+2*len;k++) sum[i][j]+=f[i][k];
            len<<=1;
        }
    }
    tree_dp(1,n,1);
    int ans=inf;
    for(int i=0;i<=(1<<n+2);i++)
        ans=min(ans,dp[1][i]);
    cout<<ans<<endl;
}```
  • mobi 2017-01-11 15:37:25

    能给下注释吗关于treedp那段代码?

  • mobi 2017-01-11 15:47:46

    特别是你是怎么确定那个叶节点的状态的怎么确定是a还是b你那样写我感觉只能分清楚是左方的点还是右方的点

  • mobi 2017-01-11 18:06:13

    前面的问题懂了 但你是怎么合在一起的呢?不会重吗?

  • mobi 2017-01-11 18:20:10

    全懂了。。。