NC20143. [JLOI2015]战争调度
描述
输入描述
第一行两个数 n;m。接下来 2^(n-1) 行，每行n-1 个数，第 i 行表示编号为 2^(n-1)-1+ i 的平民对其n-1直系上司的作战贡献度，其中第一个数表示对第一级直系上司，即编号为 (2^(n-1)-1+ i)/2 的贵族的作战贡献度 wij，依次往上。接下来 2^(n-1)行，每行n-1个数，第i行表示编号为 2^(n-1)-1+ i的平民对其n-1个直系上司的后勤贡献度，其中第一个数表示对第一级直系上司，即编号为 (2^(n-1)-1+ i)/2 的贵族的后勤贡献度 fij ，依次往上。
输出描述
一行一个数表示满足条件的最大贡献值
示例1
输入:
3 4 503 1082 1271 369 303 1135 749 1289 100 54 837 826 947 699 216 389
输出:
6701
C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 8676K, 提交时间: 2019-04-15 13:59:05
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,w[N][N],f[N][N],dp[N][N],vis[N];
void dfs(int x,int y)
{
for(int i=0;i<=(1<<y);i++)dp[x][i]=0;
if(!y)
{
for(int i=1;i<=n;i++)
if(vis[i])dp[x][1]+=w[x][i];
else dp[x][0]+=f[x][i];
return;
}
vis[y]=0;
dfs(x*2,y-1);
dfs(x*2+1,y-1);
for(int i=0;i<=1<<(y-1);i++)
for(int j=0;j<=1<<(y-1);j++)
dp[x][i+j]=max(dp[x][i+j],dp[x*2][i]+dp[x*2+1][j]);
vis[y]=1;
dfs(x*2,y-1);
dfs(x*2+1,y-1);
for(int i=0;i<=1<<(y-1);i++)
for(int j=0;j<=1<<(y-1);j++)
dp[x][i+j]=max(dp[x][i+j],dp[x*2][i]+dp[x*2+1][j]);
}
int main()
{
scanf("%d%d",&n,&m);
n--;
for(int i=0;i<(1<<n);i++)
for(int j=1;j<=n;j++)scanf("%d",&w[i+(1<<n)][j]);
for(int i=0;i<(1<<n);i++)
for(int j=1;j<=n;j++)scanf("%d",&f[i+(1<<n)][j]);
dfs(1,n);
int ans=0;
for(int i=0;i<=m;i++)ans=max(ans,dp[1][i]);
cout<<ans;
return 0;
}