「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
",ans);
return 0;
}
2019.2.25