专栏文章
题解: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)
题目大意
给定一棵以 为根,有 个结点的树,树上有 个物品。初始时你在 1 号结点,你可以花 秒向深(上)或者向浅(下)走 个节点,也可以花 秒向深(上)走 个节点,求在 秒钟之内,你最多能够拿到几个物品并返回根节点。
思路
显然树形 DP(树上背包)。
本题与一般树形 DP 不同的地方主要在于可以“连续向上走 步”。
对于一般的树形 DP 我们会设 表示在以 为根的子树中收集 个风神瞳的最小时间。
对于“连续向上走 步”的操作,我们不妨多设一维 ,表示从当前节点开始,可以使用风场连续向上跳跃的剩余步数。
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 条评论,欢迎与作者交流。
正在加载评论...