[Solution][Dynamic Programming]NOI2006 Network

沙茶就是沙茶。。。花了两天看题解,一个上午才写出来。。。效率还那么低。。。T.T

【题目】

戳这里

【来源】

BYVOID神犇

【题意】

自行脑补,花了我好长时间才读懂题。。。

【思路】

对于40%的数据,满足.

直接暴力枚举所有用户状态,并计算。
时间复杂度,好像没有人闲的用Lca的一些算法。。。
对于能够勉强卡过。

接下来探索一些规律。

观察费用系数表,发现系数都是0,1,2,我们有一种思路,可以把每个点能够带来的费用单独计算。
的非叶子节点称作点,把的非叶子节点称作点.
可以发现性质为A的叶子节点当且仅当祖先节点为节点时才累加一倍的流量值。性质为B的叶子节点同理。
至此我们可以进行树形动态规划。
定义状态表示号节点,子树中的叶子节点有个性质为的节点,的祖先状态为(一个二进制串)时的最小费用。
则有状态转移方程
若i是叶子节点,则累加i到根的路径上与i性质类似的节点权值(从k一维记录的节点状态计算),并返回。
此时是堆式存储,p的取值范围也需谨慎。
不过只是这样依然只能过暴力的40%数据。

进行优化。

可以进行记忆化搜索,存储答案时把转移方程中的j和k压成一个数,否则超空间.(参见BYVOID大牛的题解)。
这样就可以过了。

[代码]

/*
A -> 0 B -> 1
*/ 
#include<cstdio>
#include<cstring>
#include<cctype>
const int N = 1 << 11;
inline int getint()
{
    char c;
    while(!isdigit(c = getchar()));
    int tmp = c - '0';
    while(isdigit(c = getchar()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
inline int _max(int a , int b)
{
    return a > b ? a : b;
}
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
int cost[N][N] , weigh[N] , depth[N]  , save[N][N] , n , m;
bool type[N] , ext[N << 1];
int dp(int now , int num , int state)
{
    int ins , ins_dep;
    if (save[now][(num << depth[now]) | state])
        return save[now][(num << depth[now]) | state];
    bool judge = num < (1 << (n - depth[now])) - num ? 0 : 1;
    if (depth[now] == n)
    {
        int ans = 0;
        judge = num ? 0 : 1;
        if (judge != type[now])
            ans += weigh[now];
        ins = now >> 1;
        ins_dep = depth[now] - 1;
        while(ins)
        {
            if (((state >> ins_dep) & 1) == judge)
                ans += cost[now][ins];
            ins >>= 1;
            --ins_dep;
        }
        return ans;
    }
    else
    {
        int ans = 1 << 30 , tmp;
        int limit = _min(num , 1 << (n - depth[now] - 1));
        for(int i = _max(0 , num - (1 << (n - depth[now] - 1))) ; i <= limit ; ++i)
        { 
            tmp = dp(now << 1 , i , state | (judge << depth[now]));
            tmp += dp((now << 1) | 1 , num - i , state | (judge << depth[now]));
            ans = _min(ans , tmp);
        }
        save[now][(num << depth[now]) | state] = ans;
        return ans;
    }
}
int main()
{
    scanf("%d" , &n);                                     
    m = 1 << n;                                           
    int x;                                                
    register int i , j , tmpi  , tmpj;                
    for(i = 1 ; i <= m ; ++i)                             
    {                                                     
        x = getint();                                
        type[m + i - 1] = x;                      
    }                                                     
    for(i = 1 ; i < (m << 1) ; ++i)                             
    {                                                     
        tmpi = i;                                         
        while(tmpi != 1)                                  
        {                                                 
            tmpi >>= 1;                                   
            ++depth[i];                                   
        }                                                 
    }                                                     
    for(i = 1 ; i <= m ; ++i)
        weigh[m + i - 1] = getint();
    for(i = 1 ; i <= m ; ++i)
    for(j = i + 1 ; j <= m ; ++j)
    {
        x = getint();
        tmpi = m + i - 1 , tmpj = m + j - 1;
        memset(ext , 0 , sizeof(ext));
        while(tmpi)
            ext[tmpi >>= 1] = 1;
        while(tmpj)
            if (ext[tmpj >>= 1])
                break;
        cost[m + i - 1][tmpj] += x;
        cost[m + j - 1][tmpj] += x;
    }
    int ans = 1 << 30;
    for(i = 0 ; i <= m ; ++i)
        ans = _min(ans , dp(1 , i , 0));
    printf("%d" , ans);
    return 0;
}
comments powered by Disqus