本文主要是介绍计蒜之道 初赛 第二场 题解 树形dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
人人都有极客精神
人人公司是一家极为鼓励极客精神的公司，当有重要的项目需要上线但又时间太紧，甚至需要当天上线的时候，往往会挂起海盗旗开启电子日期显示，让大家可以在对时间有更明确的感知的情况下，同心协力搞定重要的项目。海盗旗下方的电子屏显示的日期形式为 YYYYMMDD （年份占 4 位、月份占 2 位、天数占 2 位）。
日期电子屏幕上每个数字对应的显示如下图：
<img src="http://res.jisuanke.com/img/nanti/428.png" <="" a="" style="box-sizing: border-box; border: 0px; vertical-align: middle; display: block; max-width: 100%; height: auto; margin: auto;">从上图可以得知每个数字对应的笔画数，比如 2 的笔画数是 5，8 的笔画数是 7，等等。人人员工小明看到了项目的启动日期 d，但是项目的结束日期没看清楚，只知道电子屏幕上项目结束日期所需的笔画数为 m，你能帮小明算出来项目执行所用的时间天数么？
输入格式
输入数据有多组。第一行输入一个整数 T (1 ≤ T ≤ 20)，表示一共有 T 组数据。
接下来每组数据 2 行，共 T * 2 行。每组第一行输入一个长度为 8 的仅包含数字的字符串 d，表示项目的启动日期，形式为 YYYYMMDD。每组第二行输入一个非负整数 m (0 ≤ m ≤ 100)，表示电子屏幕上项目结束日期所需的笔画数。输入日期保证合法。
输出格式
一共输出 T 行，每行一个整数，表示该组数据对应的项目执行所用的时间天数。如果最近的符合要求的结束日期超过 2999 年 12 月 31 日或无解则输出 -1，否则输出符合要求的最小的解。
样例1
输入：
2 20150718 30 29991231 38
输出：
85 -1
#define N 205
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
bool isYear(int year){
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)return true;
return false;
}
void add(int & year,int & month,int & day){if((month==1||month==3||month==5||month==7||month==8||month==10)&&(day==31)){month=month+1;day=1;}else if((month==4||month==6||month==9||month==11)&&(day==30)){month=month+1;day=1;}else if((month==12)&&(day==31)){year=year+1;month=1;day=1;}else if((month==2)&& isYear(year)&&(day==29)){month=month+1;day=1;}else if((month==2)&& !isYear(year)&&(day==28)){month=month+1;day=1;}else{day=day+1;}
}
char str[20];
int sum,Num[20] = {6,2,5,5,4,5,6,3,7,6},all[8060][2];
int getAll(){for(int i = 0;i<=3000;i++){int year = i;int s = 0,flag = 0;while(year){s += Num[year % 10];year /= 10;flag ++;}for(;flag < 4;flag++){s += Num[0];}all[i][0] = s;s = 0,flag = 0;year = i;while(year){s += Num[year % 10];year /= 10;flag ++;}for(;flag < 2;flag++){s += Num[0];}all[i][1] = s;}
}
int getAllNum(int year,int month,int day){return all[year][0] + all[month][1] + all[day][1];
}
bool Check(int year,int month,int day){return getAllNum(year,month,day)== sum;
}
int getNum(char c){return c - '0';
}
int main()
{int n;getAll();while(S(n)!=EOF){FJ(n){SS(str);S(sum);int year,month,day;year = getNum(str[0]) * 1000 + getNum(str[1]) * 100 + getNum(str[2]) * 10 + getNum(str[3]);month = getNum(str[4]) * 10 + getNum(str[5]);day = getNum(str[6]) * 10 + getNum(str[7]);int flag = -1,step = 0;while(true){//cout<<year<<" month "<<month<<" day "<<day<<" step "<<step<<endl;if(year == 2999 && month == 12 && day == 31){if(Check(year,month,day)){flag = step;break;}elseflag = -1;break;}if(Check(year,month,day)){flag = step;break;}add(year,month,day);step++;}printf("%d\n",flag);}}return 0;
}
自建物流的无人机实验（简单）
作为一个电子商务作为主体的公司，京东一直努力实现着自己“多、快、好、省”的承诺。其中，“快”的特质更是被京东发挥到了极致。京东建立了层级分明的物流网络，然后除了在社区里面的到户物流点，每个作为中转的物流点都是有下属的物流点的。每个物流点都有一定数量的快递员，他们每天都辛苦的在外奔波。
京东计划给一些物流点配备一种新式的无人机，用于进行货物中转、配送。因为这种无人机还在试验期，京东对每个参与测试的物流点最多都只配备一台无人机。负责这个试验的东东希望设计一种分配无人机的方案，使得对于任何一个物流点 X，以它作为最近公共上级的分配了无人机的物流点对数不小于物流点 X 的快递员数。为了节约试验预算，东东希望需要分配的无人机数量越小越好。你能帮他们求出一种分配无人机的方案吗？
<img src="http://res.jisuanke.com/img/nanti/432.png" <="" a="" style="box-sizing: border-box; border: 0px; vertical-align: middle; display: block; max-width: 100%; height: auto; margin: auto;">输入格式
输入第一行是一个整数 n，代表京东的物流点个数。
第二行是 n 个整数，第 i 个整数代表编号为 i 的京东物流点的快递员数量 valuei（0 ≤ valuei ≤ 1018）。
接下来 n-1 行，每行有2个整数 x 和 y（1 ≤ x, y ≤ n），代表物流 x 和物流点 y 之间是上下级关系（即物流点 x 是物流点 y 的上级，或物流点 y 是物流点 x 的上级）。
数据可以确保最终会形成一个树形网络，编号为 1 的物流点是没有上级的物流核心节点（树的根）。
对于简单版本，1 ≤ n ≤ 10；
对于中等版本，1 ≤ n ≤ 2000；
对于困难版本，1 ≤ n ≤ 200000。
输出格式
如果对于给定的输入存在一个可以满足要求的分配无人机的方案，则第一行输出一个整数 ans，代表最少需要多少个无人机；若 ans 不为 0，则第二行输出 ans 个整数，代表最少的方案中需无人机的 ans 个结点的编号，编号需要从小到大输出，每两个相邻整数之间有一个空格，行末没有空格（若存在多组符合要求的方案，输出任意一组即可）；若 ans 为 0，则不用输出第二行。
如果不存在满足的方案，则只在第一行输出 -1 即可。
样例1
输入：
5 6 0 0 0 0 1 2 2 3 1 4 1 5
输出：
4 1 2 4 5
提示信息
样例 1 中 1、2、4、5 这四个点两两之间共有 6 个点对，分别是(1, 2), (1, 4), (1, 5), (2, 4), (2, 5), (4, 5)，它们的最近公共上级全都是 1。满足要求的方案还有 1、3、4、5。
如果有多种最小方案，输出任意一组即可。
#define INF 9000000000
#define EPS (double)1e-9
#define mod 1000000007
#define PI 3.14159265358979
//*******************************************************************************/
#endif
#define N 205
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,a,b,land[N];
ll pri[N];
vector<int> p[N];
int Dfs(int root){ll sum = 0;int num[20] = {0},size = p[root].size(),ss = 0;FI(size){int g = p[root][i];num[i] = Dfs(g);if(num[i] == -1) return -1;ss+=num[i];}if(land[root]) {sum+= (ll)ss;}FI(size){for(int j = i+1;j<size;j++){sum+= (ll)num[i] * (ll)num[j];}}//cout<<" sum "<<sum<<" root "<<root<<" pri "<<pri[root]<<endl;if(sum >= pri[root]) return ss + land[root];else return -1;
}
bool check(int sum){//cout<<" sum "<<sum<<endl;FI(n){if((1<<i) & sum)land[i] = 1;elseland[i] = 0;//cout<<land[i]<< " ";}//cout<<Dfs(0)<<endl;return Dfs(0)!=-1;
}
int main()
{while(S(n)!=EOF){for(int i = 0;i<n;i++)p[i].clear();for(int i = 0;i<n;i++) scanf("%lld",&pri[i]);FI(n-1){S2(a,b);a--;b--;p[a].push_back(b);}int all = (1<<n);bool flag = true;FI(all){if(check(i)){flag = false;break;}}if(flag) printf("-1\n");else {int sn = 0;for(int k = 0;k<n;k++){if(land[k]) sn++;}printf("%d\n",sn);if(sn){bool isFirst = true;for(int k = 0;k<n;k++){if(land[k]){if(isFirst)printf("%d",k+1),isFirst = false;else printf(" %d",k+1);}}printf("\n");}}}return 0;
}
第二种方法，也就是树形dp的方法
dp[i]表示第i个结点，所能达到要求的最小结点数
首先，对于每个节点 x，只有在以 x 为根的子树内的点才会对最近公共祖先为 x 的点对数产生影响，所以我们在解决每个节点的时候，应该优先把它的所有子节点都解决了（因为它所有子节点为根的子树内的点都能对它产生影响）。
然后，如果两个点属于 x 同一个子节点为根的子树内，那么这两个点的最近公共祖先不为 x；反之，若它们属于不同子节点为根的子树，那么它们的最近公共祖先必定为 x。
我们在这个计算中把 x 这个点本身特殊处理成 x 的一个子树，因为它也满足其他子树内的点跟它的最近公共祖先为 x。
我们假设 x 的子节点分别为 s1，s2，…，sk，cntx 表示以 x 为根的子树内选了多少个点，dpx 表示最近公共祖先为 x 的点对对数。于是有
然后我们可以得到最近公共祖先为 x 的点对对数等于 x 为根的子树内的点对总数 –x 所有子节点为根的子树内的点对总数
写成公式就是：
于是我们在 cntx，也就是 
相同的情况下，当然是 cntsi 越平均 dpx越大了。
或者换个角度说，如果有两种方案 cnt 和 cnt‘ ，其中 cnts1< cnt’s1 ≤ cnt’ s2<cnts1，并且对于 i > 2 都有cntsi = cnt’si ，那么 cnt‘ 的方案得到的对数更大，是要优于 cnt 的方案的。
于是我们在 i 的子树中选点的时候，应该尽量朝着平均的方向选，也就是每次都贪心地选择一个未选满并且已选点数最少的子树在里面选择一个未被选过的点。如果子树里的点都选完了点对数还不够，那么显然是无解的。
这里直接用的set，复杂度为n * log(n)
#define INF 9000000000
#define EPS (double)1e-9
#define mod 1000000007
#define PI 3.14159265358979
//*******************************************************************************/
#endif
#define N 200050
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,a,b,land[N];
ll pri[N],dp[N],num[N],nodes[N];
vector<int> p[N];
multiset<pll> myset;
multiset<pll>::iterator it;
ll Dfs(int root){ll sum = 0,ss = 0;int size = p[root].size();nodes[root] = 1;FI(size){int g = p[root][i];dp[g] = Dfs(g);if(dp[g] == -1) return -1;nodes[root] += nodes[g];}FI(size){int g = p[root][i];sum += ss * dp[g];ss += dp[g];}if(sum >= pri[root]) return dp[root] = ss;else {sum += ss;ss++;if(sum >= pri[root]) return dp[root] = ss;myset.clear();FI(size){int g = p[root][i];if(dp[g] < nodes[g]){myset.insert(mp(dp[g],g));}}while(!myset.empty()){it = myset.begin();pll x = *it;myset.erase(it);sum += ss - x.first;ss++;int g = x.second;dp[g]++;if(dp[g] < nodes[g])myset.insert(mp(dp[g],g));if(sum >= pri[root]) return dp[root] = ss;}return -1;}
}
ll DfsAns(int root){int size = p[root].size();num[root] = 0;FI(size){int g = p[root][i];num[root] += dp[g];}//printf("%d %lld %lld \n",root + 1,num[root],dp[root]);if(num[root] < dp[root]){ll kk = dp[root] - num[root];land[root] = 1;kk--;for(int i = 0;i<size && kk;i++){int g = p[root][i];ll tk = min(kk,nodes[g] - dp[g]);dp[g] += tk;kk -= tk;}}else land[root] = 0;FI(size){int g = p[root][i];DfsAns(g);}return dp[root];
}
int main()
{while(S(n)!=EOF){for(int i = 0;i<n;i++) p[i].clear(),dp[i] = 0,land[i] = 0;for(int i = 0;i<n;i++) scanf("%lld",&pri[i]);FI(n-1){S2(a,b);a--;b--;p[a].push_back(b);}bool flag = true;if(Dfs(0) == -1){printf("-1\n");}else {DfsAns(0);int sn = 0;for(int k = 0;k<n;k++){if(land[k]) sn++;}printf("%d\n",sn);if(sn){bool isFirst = true;for(int k = 0;k<n;k++){if(land[k]){if(isFirst)printf("%d",k+1),isFirst = false;else printf(" %d",k+1);}}printf("\n");}}}return 0;
}
这篇关于计蒜之道 初赛 第二场 题解 树形dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
