又是一道思路清新的小清晰。
观察题目，如果我们确定了平民或者贵族的任意一方，我们便可以贪心的求出另一方，至此20分；我们发现层数十分小，那么我们就也是状压层数，用lca转移，线性dp，至此50分（好像数据很水这么打能A）；至今我们没有用到他是一棵完全二叉树，那么我们发现如果进行树dp，也就是说从子节点转移到父节点，f[i][j]，以i为根的子树里的平民有j个参战贡献最大值，我们需要确定平民的请况而且有不能状压，但是结合我们上次得出的结论，我们发现如果我们dp状态的意义为，在确定由此节点到root的所有节点的状态时，以i为根的子树里的平民有j个参战贡献最大值，我们就可以不用知道平民的情况了，就是f[i][j][k]，那么我们就可以合并上去了，然而我们发现这样不仅TLE而且MLE，但是如果我们k那一维通过枚举而实现呢，我们就可以即时转移而去掉最后一维，而且丢掉许多无效状态，然而我们发现k他从最底层到最高层呈现指数递减，我们可以兴奋一下然后认真考虑时间复杂度了：对于每一个出口也就是叶子节点我们最多出去2^10次并且每次算贡献O(10)，于是O(10*2^20)，然后每次合并——在根处2^9*2^9*1，往下走一层需要合并的点数乘2^2，合并大小除2，于是总的为层数乘点数平方即O(10*2^20)。于是总时间复杂度O(10*2^20)。
#include <cstdio> #include <cstring> #include <algorithm> #define ls (pos<<1) #define rs ((pos<<1)|1) using std::max; const int N=(1<<10)+50; int f[N][N],tw[N][20],tg[N][20],w[N][N],g[N][N]; int n,m,len,bin[20]; void read_pre(){ scanf("%d%d",&n,&m),len=1<<(n-1); for(int i=1;i<=len;++i) for(int j=1;j<n;++j) scanf("%d",&tw[i][j]); for(int i=1;i<=len;++i) for(int j=1;j<n;++j) scanf("%d",&tg[i][j]); for(int i=1;i<=len;++i) for(int j=0;j<len;++j) for(int k=1;k<n;++k) (j&(1<<(k-1)))?w[i+len-1][j]+=tw[i][k]:g[i+len-1][j]+=tg[i][k]; bin[n-1]=1; for(int i=n-2;i>0;--i)bin[i]=bin[i+1]<<1; } void dfs(int pos,int deep,int state){ if(deep==n){ f[pos][0]=g[pos][state],f[pos][1]=w[pos][state]; return; } memset(f[pos],0,sizeof(f[pos])); dfs(ls,deep+1,state|bin[deep]), dfs(rs,deep+1,state|bin[deep]); for(int i=0;i<=bin[deep];++i) for(int j=0;j<=bin[deep];++j) f[pos][i+j]=max(f[pos][i+j],f[ls][i]+f[rs][j]); dfs(ls,deep+1,state), dfs(rs,deep+1,state); for(int i=0;i<=bin[deep];++i) for(int j=0;j<=bin[deep];++j) f[pos][i+j]=max(f[pos][i+j],f[ls][i]+f[rs][j]); } void work_print(){ dfs(1,1,0);int ans=0; for(int i=0;i<=m;++i) ans=max(ans,f[1][i]); printf("%d",ans); } int main(){ read_pre(); work_print(); return 0; }