专栏文章

题解:P8917 [DMOI-R2] 风神瞳(Anemoculus)

P8917题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minh5ots
此快照首次捕获于
2025/12/02 02:20
3 个月前
此快照最后确认于
2025/12/02 02:20
3 个月前
查看原文

题解:P8917 [DMOI-R2] 风神瞳(Anemoculus)

题目大意

给定一棵以 11 为根,有 nn 个结点的树,树上有 mm 个物品。初始时你在 1 号结点,你可以花 11 秒向深(上)或者向浅(下)走 11 个节点,也可以花 11 秒向深(上)走 kk 个节点,求在 tit_i 秒钟之内,你最多能够拿到几个物品并返回根节点。

思路

显然树形 DP(树上背包)。
本题与一般树形 DP 不同的地方主要在于可以“连续向上走 kk 步”。
对于一般的树形 DP 我们会设 dpu,jdp_{u,j} 表示在以 uu 为根的子树中收集 jj 个风神瞳的最小时间。
对于“连续向上走 kk 步”的操作,我们不妨多设一维 tt,表示从当前节点开始,可以使用风场连续向上跳跃的剩余步数。

Code

具体初始化和转移等关键代码有注释。
细节较多,比较考验码力。
CPP
#include<bits/stdc++.h>
using namespace std;

#define isd(c) (c>='0'&&c<='9')  
#define For(i,a,b) for(auto i=(a);i<=(b);i++) 
#define Ror(i,a,b) for(auto i=(a);i>=(b);i--)  
#define Min(a,b) ((a)<(b) ? (a) : (b))
#define Max(a,b) ((a)>(b) ? (a) : (b))

namespace IO{
    char gc(){
        static char buf[1<<20],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++;
    }
    template<class T>void read(T &n){
        n=0;char c=gc();int k=1;
        while(!isd(c)){if(c=='-')k*=-1;c=gc();}  
        while(isd(c))n=(n<<1)+(n<<3)+(c^48),c=gc();  
        n*=k;
    }
    template<class T>void write(T n){
        if(n<0)n=-n,putchar('-');
        if(n>9)write(n/10);
        putchar((n%10)^48);
    }
}

namespace Main{
using namespace IO;
const int MAXN=2005,MAXM=505,MAXK=105,INF=1000000;
int n,m,k,q,cnt; 
int head[MAXN],     // 邻接表存图
    a[MAXN],       // 标记数组,a[u]=1 表示节点u有风神瞳
    ans[MAXN<<1],      // 答案数组,ans[t] 表示时间 t 内能收集的最大风神瞳数
    dep[MAXN],      // 深度数组,dep[u] 表示节点 u 的深度(根节点深度初始为 0)
    tot[MAXN],      // tot[u] 表示以 u 为根的子树中风神瞳总数
    c[MAXK];     // 子节点到当前节点的转移成本
// DP 状态数组:dp[u][j][t] 表示在以 u 为根的子树中收集 j 个风神瞳的最小时间
// t 表示从当前节点开始,你可以使用风场连续向上跳跃的剩余步数
int dp[MAXN][MAXM][MAXK], tmp[MAXM][MAXK];  // tmp:临时DP数组,用于子树状态合并

struct edge{
    int to,nxt;  // to:目标节点,nxt:下一条边索引
}e[MAXN<<1];

void add(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}

void dfs(int u,int f){
    if(a[u]) tot[u]=1, dp[u][1][0]=0;  // 如果 u 有风神瞳,则 tot[u]=1,表示收集 1 个风神瞳的成本为 0(初始状态)
    else tot[u]=0, dp[u][0][0]=0;       // 否则 tot[u]=0,表示收集 0 个的成本为 0
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f) continue; 
        dep[v]=dep[u]+1; 
        dfs(v,u); 
        For(j,0,tot[u]+tot[v]) For(w,0,k) tmp[j][w]=INF;
        For(j,0,tot[v]){// 遍历子节点 v 可能收集的风神瞳数量 j
            For(w,0,k) c[w]=INF;// 计算从子节点v转移到当前节点u的成本c[w](w 为风场状态)
            c[0]=dp[v][j][0]+2;  // 基础情况:从 v 走回 u(成本2步:去 v 再回 u)
            For(w,1,k-1) c[w]=dp[v][j][w-1];  // 使用风场:状态 w-1 转移到 w(相当于向上跳一步)
            // 特殊风场转移:尝试从 v 使用风场直接跳到 u 的祖先,再走回 u
            For(w,0,Min(dep[u],k-1)) c[0]=Min(c[0], dp[v][j][k-1-w] + k + 1);  // k+1成本:风场跳跃1+返回k
            if(j==0) c[0]=0;  // 如果 v 子树未收集风神瞳,转移成本为 0(无需访问 v)
            For(w,0,tot[u])  // w:u 已收集的风神瞳数
                For(t,0,k-1) // t:u 当前风场状态
                    // 状态转移:两种方式取最小值
                    // 1. 保持 u 原有状态 t,加上 v 的转移成本 tmp[0]
                    // 2. 重置 u 状态为 0,加上 v 的转移成本 tmp[t](继承 v 的状态)
                    tmp[j+w][t]=Min(tmp[j+w][t], Min(dp[u][w][t] + c[0], dp[u][w][0] + c[t]));
        }
        For(j,0,tot[u]+tot[v])
            For(w,0,k-1)
                dp[u][j][w]=tmp[j][w];
        tot[u]+=tot[v];  // 更新 u 子树的风神瞳总数
    }
}

void Main(){
    read(n),read(m),read(k),read(q);
    For(i,1,n-1){
        int u,v;
        read(u),read(v);
        add(u,v),add(v,u);
    }
    For(i,1,m){
        int u;
        read(u);
        a[u]=1;
    }
    For(i,1,n) For(j,0,m) For(w,0,k) dp[i][j][w]=INF;
    // 从根节点 1 开始 DFS
    dfs(1,0);
    For(i,1,m)
        For(j,dp[1][i][0],(n<<1))
            ans[j]=i;  // 时间 j 内能收集 i 个风神瞳

    while(q--){
        int x;
        read(x);
        // 特判时间超过 2*n ,直接输出 m ,不然会 WA
        write(x>=(n<<1) ? m : ans[x]);
        putchar('\n');
    }
}
}

int main(){
    Main::Main();
}

评论

2 条评论,欢迎与作者交流。

正在加载评论...