做购物商城网站,最新首码项目网,注册网站给谁交钱,网站服务内容怎样选思路#xff1a;这题是裸的树形dp。dp[i][j]表示第i个节点花费j步并且从子节点返回#xff0c;能得到的最大苹果数#xff1b;nback[i[j]表示第i个节点花费j步并且进入某个子节点不返回#xff0c;能得到的最大苹果数。那么我们就能得到动态方程: 根节点为u#xff0c;子节…思路这题是裸的树形dp。dp[i][j]表示第i个节点花费j步并且从子节点返回能得到的最大苹果数nback[i[j]表示第i个节点花费j步并且进入某个子节点不返回能得到的最大苹果数。那么我们就能得到动态方程: 根节点为u子节点为v dp[u][j]max(dp[u][j],dp[u][j-k-2]dp[v][k]);nback[u][j]Max(nback[u][j],nback[u][j-k-2]dp[v][k],dp[u][j-k-1]nback[v][k]);//表示对某个节点可以选择进入返回或不返回. #includeiostream
#includealgorithm
#includecstring
#includecstdio
#includevector
#define Maxn 210
using namespace std;
int vi[Maxn],val[Maxn],dp[Maxn][Maxn],n,m,nback[Maxn][Maxn];
vectorint head[Maxn];
void init()
{memset(vi,0,sizeof(vi));memset(val,0,sizeof(val));memset(dp,0,sizeof(dp));memset(nback,0,sizeof(nback));for(int i0;i110;i)head[i].clear();
}
inline int Max(int a,int b,int c)
{int tempab?a:b;return tempc?temp:c;
}
void add(int u,int v)
{head[u].push_back(v);head[v].push_back(u);
}
void dfs(int u)
{int i,v,sz,j,k;vi[u]1;szhead[u].size();int s1,s2;s1s20;for(i0;isz;i){vhead[u][i];if(vi[v]) continue;dfs(v);for(jm;j1;j--){s1s20;for(k0;kj-1;k){if(j-k2)s1max(s1,dp[u][j-k-2]dp[v][k]);s2Max(s2,nback[u][j-k-2]dp[v][k],dp[u][j-k-1]nback[v][k]);}dp[u][j]max(dp[u][j],s1);nback[u][j]max(nback[u][j],s2);}}for(i0;im;i)dp[u][i]val[u];for(i0;im;i)nback[u][i]val[u];
}
int main()
{int i,j,a,b;while(scanf(%d%d,n,m)!EOF){init();for(i1;in;i)scanf(%d,vali);for(i1;in;i){scanf(%d%d,a,b);add(a,b);}dfs(1);printf(%d\n,nback[1][m]);}return 0;
} 转载于:https://www.cnblogs.com/wangfang20/p/3252450.html
