题意：给一棵树，每个节点都有一个权值，权值只能拿一次，只让走K步，问最多能拿到多少权值
这个题目一开始没料到原来可以往回走，分析了样例才知道。之后我用DFS搜索，超时
后来一直想树形DP的状态转移，一直没想出来。后来还是看别人博客上的状态转移方程。
dp[0][rt][j+2]=max(本身,dp[0][rt][w]+dp[0][nx][j-w])//w为枚举的需要多少步，由于要从nx子节点返回，故需要比j多两步
dp[1][rt][j+2]=max(本身，dp[1][rt][w]+dp[0][nx][j-w])//走向子树后回来再一去不回，因为从子树回来需要多走两步
dp[1][rt][j+1]=max(自身，dp[1][nx][w]+dp[0][rt][j-w])//走向其他地方回来再走向子树一去不回，走子树只需要多一步
一开始没怎么理解，后来想通了，每次是枚举一个子树，已经枚举好的子树已经找到最佳状态，就是上面所谓的最佳状态，尚未枚举的子树暂且当做不存在
因为暂且未枚举的子树需要当做不存在，就要用到背包，从倒序循环步数，来保证当前找到的最佳，一定是该子树之前那个状态再加当前状态，我一开始正序循环步数，就像完全背包一样，同在一个状态里面，造成了干扰。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; vector<int> v[105]; int n,k; int val[105]; int dp[2][105][205]; int vis[105]; void clean(int n) { for (int i=0;i<=n;i++) v[i].clear(); } void dfs(int rt) { vis[rt]=1; int r=v[rt].size(); for (int i=0;i<r;i++){ int nx=v[rt][i]; if (vis[nx]) continue; dfs(nx); for (int j=k;j>=0;j--){ for (int w=0;w<=j;w++){ if (dp[0][rt][j+2]<dp[0][rt][j-w]+dp[0][nx][w]) dp[0][rt][j+2]=dp[0][rt][j-w]+dp[0][nx][w]; if (dp[1][rt][j+2]<dp[1][rt][j-w]+dp[0][nx][w]) dp[1][rt][j+2]=dp[1][rt][j-w]+dp[0][nx][w]; if (dp[1][rt][j+1]<dp[1][nx][w]+dp[0][rt][j-w]) dp[1][rt][j+1]=dp[1][nx][w]+dp[0][rt][j-w]; } } } } int main() { while (scanf("%d%d",&n,&k)!=EOF) { clean(n); int i,j; for (i=1;i<=n;i++) scanf("%d",&val[i]); for (j=1;j<n;j++) { int a,b; scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } memset(vis,0,sizeof vis); for (i=0;i<=n+5;i++){ for (j=0;j<=k+5;j++){ dp[0][i][j]=val[i]; dp[1][i][j]=val[i]; } } dfs(1); int ans=0; ans=max(dp[0][1][k],dp[1][1][k]); printf("%d ",dp[1][1][k]); } return 0; }
关于为什么最后最佳状态是dp[1][1][k]而不是dp[0][1][k]，我也不是很理解，不过我想这样说可能说得通，如果是dp[0][1][k]，则最后一步肯定是回到原点，这样没有对结果又任何贡献，最多也是==前者，所以最后最优结果应该是前者