首页 > 代码库 > UESTC 887 方伯伯的儿童节
UESTC 887 方伯伯的儿童节
树形DP问题。
定义:
1.dp[u][1]表示u这个点设立糖果发放点且u这棵子树满足条件时的最少糖果点数
2.dp[u][0]表示u这个点不设立发放点且u这棵子树满足条件时的最少糖果点数
设v1,v2……vn为u的子节点,则转移方程:
dp[u][1]= sum(min(dp[vi][1],dp[vi][0]) )+1;
dp[u][0]=sum(dp[vi][1]);
由于还要记录方案数,做一个num[][]数组随着dp[][]一起转移:
num[u][1]表示u这个点设立糖果发放点的最少点数方案。
num[u][0]表示u这个点不设立糖果发放点的最少点数方案。
分三种情况:
1.dp[v][0]<dp[v][1]: dp[u][1] += dp[v][0] num[u][1] *= num[v][0]
2.dp[v][0]=dp[v][1]: dp[u][1] += dp[v][0/1] num[u][1] *= (num[v][1]+num[v][0])
3.dp[v][0]>dp[v][1]: dp[u][1] += dp[v][1] num[u][1] *= num[v][1]
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #define Mod 1000000007 using namespace std; #define N 100007 int dp[N][2],num[N][2]; vector<int> G[N]; void dfs(int u,int fa) { dp[u][0] = 0; dp[u][1] = 1; num[u][0] = num[u][1] = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(v == fa) continue; dfs(v,u); dp[u][0] += dp[v][1]; num[u][0] *= num[v][1]; //num[u][0] num[u][0] %= SMod; if(dp[v][0] < dp[v][1]) { dp[u][1] += dp[v][0]; num[u][1] *= num[v][0]; } else if(dp[v][0] > dp[v][1]) { dp[u][1] += dp[v][1]; num[u][1] *= num[v][1]; } else { dp[u][1] += dp[v][1]; num[u][1] *= (num[v][0]+num[v][1]); } num[u][1] %= SMod; //num[u][1] } } void init() { for(int i=0;i<=100000;i++) G[i].clear(); } int main() { int t,n,i,x,y; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(i=0;i<n-1;i++) { scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } dfs(1,-1); if(dp[1][0] < dp[1][1]) printf("%d %d\n",dp[1][0],num[1][0]); else if(dp[1][0] > dp[1][1]) printf("%d %d\n",dp[1][1],num[1][1]); else printf("%d %d\n",dp[1][1],(num[1][1]+num[1][0])%SMod); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。