本文共 1777 字，大约阅读时间需要 5 分钟。
题意：你在一座古墓里盗墓，古墓在T分钟时就会倒塌，你就挂了。古墓有n个房间，每个房间都有一定价值的宝藏，n-1条边，每条边有花费的时间，形成一棵树。如果逃不出去就输出Human beings die in pursuit of wealth, and birds die in pursuit of food! 如果能逃出去，那么输出能获得的最大价值是多少。
思路：先dfs算出到n点的最短路，然后判断时间是否大于T。如果大于T就输出Human beings die in pursuit of wealth, and birds die in pursuit of food! 如果能逃出去，那么起点到终点上的点是必须走的，所以把起点到终点上的边的花费设为0，然后把剩余的时间T减去最短路花费的时间。接下来的问题就是剩余时间T能获得的最大价值。就是一个树形DP，参考了一下网上的博客。
#include #include #include #include #include #include #include #include #include #include using namespace std;const int INF=0x3f3f3f3f;const int MAXN=110;const int MAXT=550;struct Edge{ int u,v,w,nex;}edge[MAXN*2];int tot,u,v,w;int val[MAXN];int pre[MAXN];int head[MAXN];int dist[MAXN];vector lu;int dp[MAXN][MAXT];int n,ti;void addedge(int u,int v,int w){ edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].nex=head[u]; head[u]=tot++;}void dfs(int u,int pr){ for(int i=head[u];i!=-1;i=edge[i].nex) { Edge e=edge[i]; if(e.v==pr) continue; pre[e.v]=i; dist[e.v]=dist[u]+e.w; dfs(e.v,u); }}void dfs2(int u,int pre){ for(int i=0;i<=ti;i++) dp[u][i]=val[u]; for(int i=head[u];i!=-1;i=edge[i].nex) { Edge e=edge[i]; if(e.v==pre) continue; dfs2(e.v,u); for(int j=ti;j>=2*e.w;j--) for(int k=0;k<=j-2*e.w;k++) dp[u][j]=max(dp[u][j],dp[u][j-k-2*e.w]+dp[e.v][k]); }}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(pre,-1,sizeof(pre)); for(int i=0;i ti) { puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!"); continue; } for(int i=n;i!=1;i=edge[pre[i]].u) edge[pre[i]].w=edge[pre[i]^1].w=0; ti-=dist[n]; dfs2(1,-1); printf("%d\n",dp[1][ti]); } return 0;}
转载于:https://www.cnblogs.com/onlyAzha/p/4781321.html
