HDU 4276 树形DP The Ghost Blows Light
题意: 一颗树有n个结点,每个结点有若干宝物,每条路径需要若干时间.一个人开始在结点1,问能不能在规定
的时间T内到达结点n. 若能, 算出他能在规定时间T内最多拿到多少宝物.
分析: 先DFS搜出结点1到结点n的路径及必过的结点并求出最短时间t,如果t超出T,则无法到达.
否则, 将必过的路径摧毁,记下能拿到的宝物数并且总时间减去t, 将必过的结点均作为0的子结点,路径为0.
这样则将树转换成以0为根结点. 此时只需求从0点开始在剩余时间(T-t)内最多能拿到多少宝物,普通DP即可.
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=105;
vector<int>Tree[maxn];
int g[maxn][maxn],val[maxn];
int dp[maxn][maxn*5];
bool vis[maxn],vit[maxn][maxn],ok;
int n,p,m,T,ans;
void Init(){
for(int i=0;i<=n;++i) Tree[i].clear();
memset(g,0,sizeof(g));
memset(vis,false,sizeof(vis));
memset(vit,true,sizeof(vit));
ok=true; ans=0;
}
//搜索从n->1这条路径, 并将路径摧毁, 将必过的结点加到0的子结点, 把宝物值置0
bool DFS(int cnt,int t){
vis[cnt]=true;
if(cnt==1){
Tree[0].push_back(cnt); // 作为0的子结点
ans+=val[cnt]; val[cnt]=0; // 取走宝物, 并置0
if(t>=T) ok=false;
T-=t; // 空余时间
return true;
}
int len=Tree[cnt].size();
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(vis[son]) continue;
bool c=DFS(son,t+g[cnt][son]);
if(c){
vit[cnt][son]=vit[son][cnt]=false; // 将必过点之间的路径摧毁, 进行树的转换
Tree[0].push_back(cnt); // 作为0的子结点
ans+=val[cnt]; val[cnt]=0; // 取走宝物,并置0
return true;
}
}
return false;
}
void DFS_DP(int cnt){
vis[cnt]=true;
int len=Tree[cnt].size();
for(int i=0;i<=T;++i) //初始化
dp[cnt][i]=val[cnt];
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(vis[son]||!vit[cnt][son]) continue;
DFS_DP(son);
int d=g[cnt][son]*2;
for(int j=T;j>=d;--j)
for(int k=j-d;k>=0;--k)
dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);
}
}
int main(){
while(~scanf("%d%d",&n,&T)){
Init();
for(int i=1;i<n;++i){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
Tree[a].push_back(b);
Tree[b].push_back(a);
}
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
DFS(n,0);
if(!ok){
puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
continue;
}
memset(dp,0,sizeof(dp));
memset(vis,false,sizeof(vis));
DFS_DP(0); // 从根结点0开始遍历
ans+=dp[0][T];
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=105;
vector<int>Tree[maxn];
int g[maxn][maxn],val[maxn];
int dp[maxn][maxn*5];
bool vis[maxn],vit[maxn][maxn],ok;
int n,p,m,T,ans;
void Init(){
for(int i=0;i<=n;++i) Tree[i].clear();
memset(g,0,sizeof(g));
memset(vis,false,sizeof(vis));
memset(vit,true,sizeof(vit));
ok=true; ans=0;
}
//搜索从n->1这条路径, 并将路径摧毁, 将必过的结点加到0的子结点, 把宝物值置0
bool DFS(int cnt,int t){
vis[cnt]=true;
if(cnt==1){
Tree[0].push_back(cnt); // 作为0的子结点
ans+=val[cnt]; val[cnt]=0; // 取走宝物, 并置0
if(t>=T) ok=false;
T-=t; // 空余时间
return true;
}
int len=Tree[cnt].size();
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(vis[son]) continue;
bool c=DFS(son,t+g[cnt][son]);
if(c){
vit[cnt][son]=vit[son][cnt]=false; // 将必过点之间的路径摧毁, 进行树的转换
Tree[0].push_back(cnt); // 作为0的子结点
ans+=val[cnt]; val[cnt]=0; // 取走宝物,并置0
return true;
}
}
return false;
}
void DFS_DP(int cnt){
vis[cnt]=true;
int len=Tree[cnt].size();
for(int i=0;i<=T;++i) //初始化
dp[cnt][i]=val[cnt];
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(vis[son]||!vit[cnt][son]) continue;
DFS_DP(son);
int d=g[cnt][son]*2;
for(int j=T;j>=d;--j)
for(int k=j-d;k>=0;--k)
dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);
}
}
int main(){
while(~scanf("%d%d",&n,&T)){
Init();
for(int i=1;i<n;++i){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
Tree[a].push_back(b);
Tree[b].push_back(a);
}
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
DFS(n,0);
if(!ok){
puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
continue;
}
memset(dp,0,sizeof(dp));
memset(vis,false,sizeof(vis));
DFS_DP(0); // 从根结点0开始遍历
ans+=dp[0][T];
printf("%d\n",ans);
}
return 0;
}
补充：软件开发 , C++ ,
