本文共 2605 字，大约阅读时间需要 8 分钟。
1、
2、题目大意：
有一棵苹果树，树上有n个结点，每个结点上都有一定量的苹果，现在从一号结点出发，只允许走k步，求最多可以获得多少个苹果
分析：
首先可以确定是一棵树上的操作，问题在于在这棵树上可以前进可以后退，每走一步都算一步，那么我们就有两种状态
dp[u][j][0],以u为根节点出发走j步，不返回u点的最大值
dp[u][j][1],以u为根节点出发走j步，返回u点的最大值
对于u的子节点v来说，他俩有四种情况，实际上三种可行
u v
0 0 u不返回，v也不返回，这种情况不存在
0 1 u不返回，v返回，即最终停留在u的其他子树上（除了v）,那么多走2步（u--v,v---u）
1 0 u返回，v不返回，即最终停留在v这可子树上，那么将多走一步（u--v）
1 1 u返回，v返回，即最终 停留在u上，那么将多走2步（u--v,v--u）
状态转移方程
dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[vv][k][1]);//u不返回，vv返回，留在u的其他子树 dp[u][j+1][0]=max(dp[u][j+1][0],dp[u][j-k][1]+dp[vv][k][0]);//u返回，vv不返回，留在vv子树上 dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[vv][k][1]);//u返回，vv返回，留在u点上
3、AC代码：
#include#include #include using namespace std;#define N 1005int w[N];int v[N];int head[N];int next[N];int tot;int dp[N][N][2];int num[N],tmp[N],m;void add_edge(int a,int b){ v[tot]=b; next[tot]=head[a]; head[a]=tot++;}void dfs(int u,int fa){ for(int i=0;i<=m;i++) dp[u][i][0]=dp[u][i][1]=num[u]; //dp[u][i][0]不返回u点，dp[u][i][1]返回u点 for(int i=head[u]; i!=-1; i=next[i]) { int vv=v[i]; if(vv!=fa) { dfs(vv,u); for(int j=m;j>=0;j--) { for(int k=0;k<=j;k++) { dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[vv][k][1]);//u不返回，vv返回，留在u的其他子树 dp[u][j+1][0]=max(dp[u][j+1][0],dp[u][j-k][1]+dp[vv][k][0]);//u返回，vv不返回，留在vv子树上 dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[vv][k][1]);//u返回，vv返回，留在u点上 } } } }}int main(){ int n,a,b; while(scanf("%d%d",&n,&m)!=EOF) { tot=0; memset(next,-1,sizeof(next)); memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); for(int i=1; i<=n; i++) { scanf("%d",&num[i]); } for(int i=1; i
用vectorAC代码：