JZOJ 3166. 【GDOI2013模拟3】火星菌（DP）

JZOJ 3166.【GDOI2013模拟3】火星菌

题目

Description

科学家发现火星上有一种奇怪的细菌，每天产生的新细菌数量是$2$的幂，因为每天新产生的细菌会在下一天产生两个新细菌，第一天只有一个细菌。因此，第一天有$1$个细菌，第二天有$2$个，第三天有$4$个，。。。，第$k+1$天有$2^k$ 个细菌。用$1$到$2^k$对这$2^k$个细菌进行编号，同时满足：

第$k$天的细菌的子孙分别是$(1,2)，(3,4)，(5,6)，。。。,(2^k-1,2^k)$

第$k-1$天的细菌的子孙分别是$(1,2,3,4)，(5,6,7,8)，。。。，(2^k-3,2^k-2,2^k-1,2^k)$

第$k-2$天的细菌的子孙分别是$(1,2,3,4,5,6,7,8)，。。。，(2^k-7,2^k-6,2^k-5,2^k-4,2^k-3,2^k-2,2^k-1,2^k)$

。。。

第$2$天的细菌的子孙分别是$(1,2,3,...,2^{k-1})，(2^{k-1}+1,2^{k-1}+2,...,2^k)$

其中括号括起来的集合里面的元素是一个细菌的子孙，以上对第$k+1$天的$2^k$个细菌的编号方式满足：前面任何一天的任何一个细菌的子孙编号都是连续的数字。

但编号方法不是唯一的，可能有很多种方法，现在给定任意两个编号$i$和$j$之间的权值$w[i][j]$，要求找到$1$到$2^k$的一个排列$A_1,A_2,....,A_{2^k-1},A_{2^k}$满足前面任何一天的细菌的子孙都对应着一段连续的数字，同时要求排列的权值$w[A_1][A_2]+w[A_2][A_3]+....+w[A_{2^k-1}][A_{2^k}]$最小。

Input

第一行输入一个整数$k(1\le k\le 9)$

接下来$2^k$行，每行输入$2^k$个数，范围在$0$到$10^6$之间，表示$w[i][j]$。

当然输入保证$w[i][j]=w[j][i]$，$w[i][i]=0$.

Output

输出一个数表示满足条件的$1$到$2^k$的排列的最小权值。

Sample Input

输入1：
2
0 7 2 1
7 0 4 3
2 4 0 5
1 3 5 0

输入2：
3
0 2 6 3 4 7 1 3
2 0 7 10 9 1 3 6
6 7 0 3 5 6 5 5
3 10 3 0 9 8 9 7
4 9 5 9 0 9 8 4
7 1 6 8 9 0 8 7
1 3 5 9 8 8 0 10
3 6 5 7 4 7 10 0

Sample Output

输出1：
13

输出2：
32

Data Constraint

100%的数据满足$1\le k\le 9$.

Hint

样例1 中满足条件的排列有$(1,2,3,4)、(1,2,4,3)、(2,1,3,4)、(2,1,4,3)、(3,4,1,2)、(3,4,2,1)、(4,3,1,2)、(4,3,2,1)$对应的权值分别为$16、15、14、13、13、15、14、16$，权值最小的排列为$(2,1,4,3)$和$(3,4,1,2)$，都是$13$.

题解

• 这道题目的描述太太太太太复杂了！！
• 简化题面：
• 建一棵满二叉数（类似一棵线段树），
• 第$0$层——$[1,2^k]$
• 第$1$层——$[1,2^{k-1}]，[2^{k-1}+1,2^k]$
• ……
• 第$k$层——$1,2,3\dots \dots 2^k$
• 每个节点有两个子树（类似线段树），允许把任何一个节点的左右子树进行交换，最后第$k$层不一定是$1-2^k$升序排列，可能是乱序的。
• 问经过这样的随意交换后，最小的第$k$层的序列每相邻两个数的$w$值之和。
• 考虑用DP解决：
• 设$f[i][j]$为最后一层第$i$个数为$j$的最小值，转移不难想到：
  $$f[i][j]=min(f[i][j],f[i-1][h])$$
• （其中$h$是枚举的）
• 这成为一个不易解决的问题，$h$的范围是多少？
• 把整个序列想象成很多块，
• $1$个大小为$2^k$的块，$2$个大小为$2^{k-1}$的块……$2^k$个大小为$1$的块，按从左到右的顺序分开。
• 找到一个$p$，使$i$和$i-1$不在同一个大小为$p$的块中，最大化$p$.（$p$一定是$2$的幂数）
• 接着看$j$所在的大小为$p$的块是第$x$个，找到$x$.
• 那么若$x$为奇数，$h$的范围就是第$x+1$个大小为$p$的块的范围；
• 若$x$为偶数，$h$的范围就是第$x-1$个大小为$p$的块的范围。
• 举个例子：
• 当前$i=5，j=35$
• 发现$i$和$i-1$在同一个大小为$8$的块中$[1,8]$，不在同一个大小为$4$的块中$[1,4]$和$[5,8]$，则$p$为$4$.
• $j$在第$9$个大小为$4$的块中$[33,36]$，那么$h$的范围就是$[37,40]$.
• 先把题目大意理解清楚，题解多看几遍，自己画一画图，很快就会明白的！

代码

#include<cstdio>
#include<cstring>
using namespace std;
int e[10],w[520][520],f[520][520];
int main()
{
	int n,i,j,k;
	e[0]=1;
	for(i=1;i<=9;i++) e[i]=e[i-1]*2;
	scanf("%d",&n);
	for(i=0;i<e[n];i++)
		for(j=0;j<e[n];j++) scanf("%d",&w[i][j]);

	for(i=0;i<e[n];i++) f[0][i]=0;
	
	for(i=1;i<e[n];i++)
		for(j=0;j<e[n];j++)
		{
			f[i][j]=2147483647;
			int l,r;
			
			for(k=n;k>=0;k--)
			{
				if(i/e[k]!=(i-1)/e[k])
				{
					int x=j/e[k];
					x^=1;
					l=x*e[k];
					r=l+e[k]-1;
					break;
				}
			}
			
			for(k=l;k<=r;k++) if(f[i-1][k]+w[j][k]<f[i][j]) f[i][j]=f[i-1][k]+w[j][k];
		}
		
	int ans=2147483647;
	for(i=0;i<e[n];i++) if(f[e[n]-1][i]<ans) ans=f[e[n]-1][i];
	
	printf("%d",ans);
	return 0;
}