「JLOI2015」战争调度 解题报告

「JLOI2015」战争调度

感觉一到晚上大脑就宕机了...

题目本身不难，就算没接触过想想也是可以想到的

这个满二叉树的深度很浅啊，每个点只会和它的\(n-1\)个祖先匹配啊

于是可以暴力枚举祖先链的选择

然后处理某个点\(i\)时，已经枚举了\(i\)到根的祖先的选择

这时候我们发现枚举\(i\)后，左右儿子的贡献的独立的，然后左右儿子的选择对上面是没有影响的

可以直接设\(dp_{i,j}\)表示\(i\)子树\(j\)黑点的最大值

然后直接子树合并两个儿子就可以了

复杂度？

\(T(n)=2(2T(n-1)+2^n)\)

好像是这个，化出来差不多是\(O(n2^{2n})\)

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

using std::max;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

#define ls id<<1

#define rs id<<1|1

const int N=1<<10;

int dp[N][N],w[N][N],f[N][N],cho[N],n,m;

void dfs(int id,int k)

{

    for(int i=0;i<=k;i++) dp[id][i]=0;

	if(k==1)

	{

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

		{

			int fa=id>>i;

			if(cho[fa]) dp[id][1]+=w[id][fa];

			else dp[id][0]+=f[id][fa];

		}

		return;

	}

	cho[id]=0;

	dfs(ls,k>>1),dfs(rs,k>>1);

	for(int i=0;i<=k>>1;i++)

		for(int j=0;j<=k>>1;j++)

			dp[id][i+j]=max(dp[id][i+j],dp[ls][i]+dp[rs][j]);

	cho[id]=1;//w[i][j]

	dfs(ls,k>>1),dfs(rs,k>>1);

	for(int i=0;i<=k>>1;i++)

		for(int j=0;j<=k>>1;j++)

			dp[id][i+j]=max(dp[id][i+j],dp[ls][i]+dp[rs][j]);

}

int main()

{

	read(n),read(m);

	int k=1<<n-1;

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

	{

		int id=k-1+i;

		for(int j=1;j<n;j++)

			read(w[id][id>>j]);//<=m

	}

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

	{

		int id=k-1+i;

		for(int j=1;j<n;j++)

			read(f[id][id>>j]);

	}

	dfs(1,k);

	int ans=0;

	for(int i=0;i<=m;i++) ans=max(ans,dp[1][i]);

	printf("%d\n",ans);

	return 0;

}

---

2019.2.25