285484026

【XJOI tree】树上背包+奇怪优化
题解:考这场考试的前一天晚上逛大神博客,看见别人有写树上背包,嗯,一笑而过了。。。。结果第二天XJOI的提高组模拟...
扫描右侧二维码阅读全文
01
2018/10

【XJOI tree】树上背包+奇怪优化

20161031173023117.png
20161031173042133.png
题解:
考这场考试的前一天晚上逛大神博客,看见别人有写树上背包,嗯,一笑而过了。。。。结果第二天XJOI的提高组模拟赛就考了。于是不会,然后今天在上课的时候发呆的时候,自己脑补出来树上背包的做法。嗯,看了一下大神的博客,我发现大神的树上背包是用的记忆化搜索,我最开始的想法是基于拓扑排序从下往上dp,嗯,复杂了,改进了一下我的方法。

一般的树上背包:(60分解法)
定义:dpi为到点i已经装入j个点所能获得的最大价值。

然后我们的状态转移方程为: dpi = max(dpi,dpi + dp[son[i]][k]);
要遍历N个点,显然j要从1-lim循环,k也要从1-lim循环。所以时间复杂度为O(N*lim^2)
可以过N <= 100的数据,对于本题60分是够了的。PS:对于善良的出题人,也都是可以AC的。

优化一下的树上背包:(100分解法)
同样定义:dpi为到点i已经装入j个点所能获得的最大价值,再多定义一个sz[i]用来表示i的以搜索子树大小;

然后我们的状态转移方程为: dpi = max(dpi,dpi + dp[son[i]][k]);

但是我们稍微思考一下我们每一次状态转移的时候都不用遍历所有的状态,因为我们有效的状态没有那么多个,画个图发现我有效的状态,只有我们前面搜索的所有树上所有点,也就是sz[i],然后我可以更新我这个节点的子树的状态为sz[son[i]],这样的话更新我这个状态的时间复杂度就由原来的lim^2变成了蜜汁时间复杂度,感觉这儿应该涉及到均摊和期望?反正我不太会算,请各位大神解答一下感激不尽

对了别人官方题解给出的代码和我的解答是一样的,但是按照我的理解似乎官方解答和我的解答的思路就不一样。

官方题解:
有兴趣的可以去别人哪儿看,我就不发了。
XJOI题解

代码:

#include <iostream>
#include <cstdio>

const int MAXN = 3005,INF = 1e9;

using namespace std;

int n,k,e = 1,ans;
int head[MAXN],d[MAXN],dp[MAXN][MAXN],sz[MAXN];
bool vis[MAXN];

struct node{
    int v,next;
}edge[10*MAXN];

inline void addedge(int u,int v)
{
    edge[e] = (node){v,head[u]};head[u] = e++;
}

inline void init()
{
    scanf("%d %d",&n,&k);
    
    for(int i = 1;i <= n;i++) scanf("%d",&d[i]);
    
    int u,v;
    
    for(int i = 1;i < n;i++){
        scanf("%d %d",&u,&v);
        addedge(u,v);addedge(v,u);
    }
}

int dfs(int u,int fa)
{
    sz[u] = 0;dp[u][0] = 0;
    
    for(int i = head[u];i;i = edge[i].next)
    {
        int v = edge[i].v;
        if(v != fa){
            dfs(v,u);
            
            for(int j = sz[u];j >= 0;j--)
                for(int k = 1;k <= sz[v];k++)
                    dp[u][j+k] = max(dp[u][j+k],dp[u][j] + dp[v][k]);
                    
            sz[u] += sz[v];
        }
    }
    
    sz[u]++;
    
    for(int i = sz[u];i >= 1;i--)
        dp[u][i] = dp[u][i-1] + d[u];
    
    dp[u][0] = -INF;
}

int main()
{
    init();
    
    for(int i = 1;i <= n;i++)
        for(int j = 0;j <= k;j++)
            dp[i][j] = -INF;
    
    dfs(1,0);
    
    ans = -INF;
    
    for(int i = 1;i <= k;i++)
        ans = max(dp[1][i],ans);
    
    printf("%d",ans);
    
    
    return 0;
}
Last modification:October 1st, 2018 at 09:55 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment