解题报告 P3574 [POI2014]FAR-FarmCraft

题目内容

P3574

大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。

解题思路

可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i 的时间安装电脑, f_i 表示以 i 为根的子树全部安装好需要的最短时间,g_i 表示开车遍历以 i 为根的子树需要的最短时间,则有如下的方程:

f_i=\max(c_i,f_j+g_i+1)\
g_i\leftarrow g_i+g_j+2

其中 ji 的子节点,且 g_i 是动态更新的,就是遍历 j 之前的所有子树需要花的总时间。意思就是,对于一个 i 为根的子树,显然,第一次到 i 点的时候就让这里的村民开始装电脑得到的肯定更优,用这个时间与后面遍历下面节点的时间相比,总花费的时间是两者中间取最大的。而 f_j+g_i+1 的意义为,遍历过 j 节点之前的所有子节点需要的时间和 g_i 加上 j 节点需要的最短时间 f_j,至于 +1 就是从 i 节点走到 j 节点的花费。

而至于为什么是 +1 而不是 +2,是因为 \forall i:f_i-g_i\ge1,即等待的时间必然大于等于 1,所以只需要考虑从 i 进入 j 的时间,即为 1,而返回来的 1 的时间是被 f_j 覆盖掉的

不难发现,遍历的顺序会影响最终的结果,所以考虑贪心:可以发现,f_i-g_i 这段时间就是拿来等待的,做过接水问题的都知道要先处理等待时间大的,于是在转移前将子节点按照 f_i-g_i 排序即可。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=500010;
int n,c[maxn],f[maxn],g[maxn],tmp[maxn];
vector<int> G[maxn];

inline void ins(int a,int b)
{
    G[a].push_back(b);
    G[b].push_back(a);
    return;
}

inline bool cmp(int x,int y)
{
    return f[x]-g[x] > f[y]-g[y];
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(now!=1)//管理员的电脑最后装
        f[now]=c[now];
    int cnt=0;
    for(auto i:G[now])
        if(i!=fa)
            dfs(i,now);
    //一定要先遍历后记录儿子节点,不然会被下面的节点覆盖掉
    for(auto i:G[now])
        if(i!=fa)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],f[tmp[i]]+g[now]+1),
        g[now]+=g[tmp[i]]+2;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    int a,b;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        ins(a,b);
    }
    dfs(1,0);
    printf("%d\n",max(c[1]+g[1],f[1]));//在最后也要注意
    return 0;
}

解题报告 P6082 [JSOI2015]salesman

题目内容

P6082

大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质,到达这个点进入了一次,去到每一棵子树再回来又是进入这个点一次,所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优,需要使用贪心思想,当将一个节点的所有子树的信息处理完之后,将其从大到小排序,取前面的限制次数减一个并加起来(当然如果加到负数就肯定不加了)。

至于解的唯一性,注意到如果一个子树下的某个子树的解不唯一,那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树,这个子树的答案为 0,则走与不走这个子树的效果是相同的,答案就会不唯一。还有,如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同,说明可以选 a 也可以选 b,效果都是一样的,也会产生多解。

代码如下:

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了,说明会产生负贡献,直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同,则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}

解题报告 P2014 [CTSC1997]选课

题目内容

P2014

大意:选课,其中选某些课必须选一个先修课,每门课有一个学分,求选 m 门课达到的最大学分

解题思路

树上的 0-1 背包问题,具体的思路还是递归求解每一棵子树的最优解。

f_{now,j} 表示以 now 节点为根的子树选 j 门课(包括 now 本身)能达到的最大学分。则有状态转移方程

f_{now,j}=\max\lbrace f_{now,j},f_{x,k}+f_{now,j-k} \rbrace

其中 xnow 的儿子节点,k\in[0,j)j\in[1,m+1]

还有一点需要注意的是我们可以假设出一个 0 节点,作为整棵树的根,方便进行处理。

#include <cstdio>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=305;
int n,m,s[maxn],f[maxn][maxn];
vector<int> son[maxn];

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void dfs(int now)
{
    for(auto i:son[now])
    {
        dfs(i);
        for(int j=m+1;j>=1;--j)
            for(int k=0;k<j;++k)
                f[now][j]=max(f[now][j],f[now][j-k]+f[i][k]);//转移
    }
    return;
}

int main()
{
    n=read(),m=read();
    for(int i=1,k;i<=n;i++)
    {
        k=read(),s[i]=read();
        f[i][1]=s[i];//初始值
        son[k].push_back(i);
    }
    dfs(0);
    printf("%d\n",f[0][m+1]);
    return 0;
}

解题报告 P1352 没有上司的舞会

题目内容

P1352

大意:某大学职员的从属关系是一棵树,有一场舞会,每人都有特定的快乐指数 r_i,但如果一个职员的直接上司参加了舞会,那么他一定就不会来了,求最大快乐指数和。

解题思路

经典的树形 dp,一般树形的 dp 都是每个子树每个子树一层层递归上去,现在考虑设计状态和状态转移:

f_{i,k} 表示以 i 号职员为树根的子树在 i 号职员去( k=1 )或不去( k=0 )的情况下能达到的最大快乐指数。

这样的正确性是显然的,由于所有员工的关系是树形,所以当一个子树的最优状态计算出来后,子树中的员工来或者不来就关系不大了,这个 dp 的无后效性体现在这里,最优子结构也可以体现:子树下面的子树达到最优了,显然整棵子树也是最优的。

方程式如下,x 一定为 i 的直属员工:

f_{i,0}=\sum\max(f_{x,0},f_{x,1})

如果这个员工 i 不去的话,总的快乐指数就是下面的所有员工去或不去能达到的最大快乐指数之和。

否则如果这个员工要去的话,那下面的直接员工都不会去,就是

f_{i,1}=\sum f_{x,0}+r_i

具体的实现就是 dfs 一层一层递归下去就可以了,当然不要忘记一开始确定树根的位置

#include <cstdio>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=6e3+5;
vector<int> tree[maxn];
int r[maxn],n,fa[maxn],f[maxn][2];

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void dfs(int s)
{
    for(auto i:tree[s])//遍历子树
    {
        dfs(i);
        f[s][0]+=max(f[i][0],f[i][1]);
        f[s][1]+=f[i][0];
    }
    f[s][1]+=r[s];
    return;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        r[i]=read();
    int l,k;
    for(int i=1;i<n;i++)
    {
        l=read(),k=read();
        tree[k].push_back(l);
        fa[l]++;//记录入度
    }
    int s;
    for(int i=1;i<=n;i++)
        if(!fa[i])//入度为0的节点就是根
        {
            s=i;
            break;
        }
    dfs(s);
    printf("%d\n",max(f[s][0],f[s][1]));
    return 0;
}