#1945. [Ceoi2007]Royaltreasury

Online Judge：Bzoj-1945

Label：树形Dp，高精度

题目描述

在很久很久以前的一个王国里，王国的财产开始变得越来越少。国王决定改变这种情况，然后他发明了一种新的系统。系统职员要求两两成对（为了避免行贿），每一对由一个职员及他的下属组成。你的任务就是在满足这种组成方式结构的前提下，计算出能够按照这种方式组成的最大的对数，和可能的方法数。

这项任务是由George Skinflint领导的。每个职员都有0个,1个或者更多的下属，并且每个职员都只有一个单独的上司（除了George Skinglint）。职员的人数不会超过1 000。你的任务就是，按照由职员及他的下属组成的方法，计算出能够组成的对数的最大值。另外，你也要计算最大值可能的组成的方式有多少种。注意一些职员不需要成对。

输入

第一行包含一个数字N，表示职员的数目，1≤N≤1000。职员按照特殊的ID号码进行标号，号码为1~N。Skinflint的号码为1。接下来N行对应相应的职员：包含其ID号和一个数字K表示他的下属的数目，0≤K≤999，接下来给出他的K个职员的ID号，中间由空格分隔。并且保证所有职员不会比他的上司先出现。

输出

输出包含两行。第一行包含一个单独的数字，代表职员能形成的最多的对数。第二行表示在多数最多的情况下，有多少种形成方式。

样例输入

样例输出

3

4

题解：

题目大意就是给定一棵n个节点的树，让你将父亲节点和儿子节点配对，问最多能组几对，且能达到这个最大值的配对方案有几种。

由于n<=1000，考虑树形Dp，定义状态：\(dp[x][0]\)表示不选x时，x的子树（包含x）最多能组的对数，\(dp[x][1]\)表示选x时，x的子树（包含x）最多能组的对数。相应的定义数组\(cnt[x][0],cnt[x][1]\)表示不选/选x时，达到最大值的方案数。

我们知道，当解决完x的子树后，就可以得到上述四个值，由于只有最优情况会对父亲节点做出贡献，为了方便向上回溯统计，直接在得到上述四个值后选出最优答案。具体实现如下，我们把最优解存在\(dp[x][1],cnt[x][1]\)上，那么最终答案就是\(dp[1][1],cnt[1][1]\)。

也就是说，只有当处于x这一层时，\(dp[x][1],cnt[x][1]\)才表示选择x的状态。

if(dp[x][1]<dp[x][0]){

        dp[x][1]=dp[x][0];

          cnt[x][1]=cnt[x][0];

    }

else if(dp[x][1]==dp[x][0])cnt[x][1]=cnt[x][1]+cnt[x][0];

接下来考虑如何转移。设当前层为x。

Status1:当不选x时，那么x的儿子选或不选都可以，那直接每个儿子都选最优情况，只要将\(cnt[x][0]*=cnt[son][1],dp[x][0]+=dp[son][1]\)即可，注意由于在搞x之前已经先递归子树了，这里的\(cnt[son][1],dp[son][1]\)就已经表示儿子的最优情况(联系上面对状态的定义)。
Status2:如果选择x情况就比较复杂了，必须选且仅选一个儿子与x组对，而剩下的儿子可以不选或选——选的话就是那个儿子跟他的儿子组对了，这与x无瓜。那具体怎么处理呢？？我们在求Status1的时候已经得到了\(dp[x][0]\),那么只要将其中一个儿子p与x组对即可，其他儿子还是选最优情况。如何确定与x组对的儿子p呢，设p的最优解为best,当p不选时(如果p不选的话我们就可以把他和x组一对了)的最优情况为unchoose，那么只要找一个best-unchoose最小的即可——（注意可能存在多个p，此时对\(dp[x][1]\)并无影响，但对方案数\(cnt[x][1]\)会有影响，下面将会讨论到），我们统计这个最小差值mi，则\(mi=min(dp[son][1]-dp[son][0])\)，那么\(dp[x][1]=dp[x][0]-mi+1\)，后面那个1是x与p新组的对数。那么如何求\(cnt[x][1]\)呢？？我们根据那个mi值找到儿子p（可能会存在多个），然后根据下面的过程统计，详见注释。

for(int i=0; i<e[x].size(); i++) {

		int y=e[x][i];//上文提到的儿子p

		if(mi==dp[y][1]-dp[y][0]) {

			BigInt s;s.init(1);

			for(int j=0; j<e[x].size(); j++) {//除了p的其他儿子

				int z=e[x][j];

				if(z==y)s=s*cnt[z][0];

				else s=s*cnt[z][1];//统计方案数

			}

			cnt[x][1]=cnt[x][1]+s;//由于可能存在多个儿子p，根据加法原理统计

		}

}

到此此题就结束了，但是——，发现cnt方案数可能会很大，所以得用高精，而至于dp的值嘛不会超过n<=1000，所以int就够了。ps:下面的高精模板挺好用的233

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

const int P=10000;

int n,dp[N][2];

vector<int>e[N];

struct BigInt {

	int len,a[100];

	BigInt() {

		len=0;

		memset(a,0,sizeof(a));

	}

	void init(int x) {

		memset(a,0,sizeof(a));

		len=0;

		do {

			a[++len]=x%P;

			x/=P;

		} while(x);

	}

	void output() {

		printf("%d",a[len]);

		for(int i=len-1; i>=1; i--)printf("%04d",a[i]);

		puts("");

	}

	BigInt operator *(BigInt x) {

		BigInt now;

		now.len=len+x.len-1;

		for(int i=1; i<=len; i++)

			for(int j=1; j<=x.len; j++)now.a[i+j-1]+=a[i]*x.a[j];

		for(int i=1; i<=now.len; i++) {

			now.a[i+1]+=now.a[i]/P;

			now.a[i]%=P;

		}

		while(now.a[now.len+1])now.len++;

		return now;

	}

	BigInt operator +(BigInt x) {

		BigInt now;

		now.len=max(len,x.len);

		for(int i=1; i<=now.len; i++)now.a[i]=x.a[i]+a[i];

		for(int i=1; i<=now.len; i++) {

			now.a[i+1]+=now.a[i]/P;

			now.a[i]%=P;

		}

		while(now.a[now.len+1])now.len++;

		return now;

	}

} cnt[N][2];

void dfs(int x) {

	cnt[x][0].init(1);

	int mi=1e9;

	for(int i=0; i<e[x].size(); i++) {

		int y=e[x][i];

		dfs(y);

		cnt[x][0]=cnt[x][0]*cnt[y][1];

		dp[x][0]+=dp[y][1];

		mi=min(dp[y][1]-dp[y][0],mi);

	}

	dp[x][1]=dp[x][0]-mi+1;

	for(int i=0; i<e[x].size(); i++) {

		int y=e[x][i];

		if(mi==dp[y][1]-dp[y][0]) {

			BigInt s;

			s.init(1);

			for(int j=0; j<e[x].size(); j++) {

				int z=e[x][j];

				if(z==y)s=s*cnt[z][0];

				else s=s*cnt[z][1];

			}

			cnt[x][1]=cnt[x][1]+s;

		}

	}

	if(dp[x][1]<dp[x][0]) {

		dp[x][1]=dp[x][0];

		cnt[x][1]=cnt[x][0];

	} else if(dp[x][1]==dp[x][0])cnt[x][1]=cnt[x][1]+cnt[x][0];

}

int main() {

	scanf("%d",&n);

	for(int i=1,id,k,u; i<=n; i++) {

		scanf("%d%d",&id,&k);

		for(int j=1; j<=k; j++) {

			scanf("%d",&u);

			e[id].push_back(u);

		}

	}

	dfs(1);

	printf("%d\n",dp[1][1]);

	cnt[1][1].output();

}

巴特西

[Ceoi2007]Royaltreasury

#1945. [Ceoi2007]Royaltreasury

题目描述

输入

输出

样例输入

样例输出

题解：

最新文章

热门文章