「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

04-17 12:07