自动搬运

查看原文

来自洛谷，原作者为

	zpy12345 普普通通

搬运于2025-08-24 22:31:18，当前版本为作者最后更新于2025-08-11 16:29:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[COCI 2012/2013 #1] MARS

本篇题解的思路应该是效率最高的思路。

思路

这么复杂的题目，当然要用 DP 了。

首先，我们可以依照常规设出状态 $dp_{i}$ 表示对前 $i$ 个细菌进行编号，最小的长度。显然无法转移。我们注意到，最小的长度在转移时，需要知道上一个位置是什么值，才好求出排斥值进行转移。故设 $dp_{i,j}$ 表示对前 $i$ 个细菌进行编号，其中最后一个细菌（即位置 $i$ 的细菌）编号为 $j$，最小的长度。

可以发现，如果对编号后的序列按下标每两个划分为一组，那么编号为 $\{1,2\},\{3,4\},\{5,6\},\cdots,\{2^K-1,2^K\}$ 的细菌一定在同一组。如果不是，例如在 $\{a_{1},a_{2},a_{3},\cdots,a_{2^K-1},a_{2^k}\}$ 中，$a_{2x}=2y-1$ 且 $a_{2x+1}=2y$，那么 $a_{2x-1}=2y-2$，$a_{2x-2}=2y-3\cdots$。这里 $2y-2$ 为偶数，$2x-1$ 为奇数，显然无法刚好填满，与题意矛盾。

故如果对编号后的序列按下标每两个划分为一组，那么编号为 $\{1,2\},\{3,4\},\{5,6\},\cdots,\{2^K-1,2^K\}$ 的细菌一定在同一组。同理可证:

如果对编号后序列的序列按下标每 $2^x$ 个进行划分，那么编号为 $\{1,2,\cdots,2^x-1,2^x\},\{2^x+1,2^x+2,\cdots,2^{x+1}-1,2^{x+1}\},\cdots,\{2^K-2^x+1,2^K-2^x+2,\cdots,2^K-1,2^K\}$ 的细菌一定在同一组。

有了以上结论，可以发现，如果第 $i$ 位编号为 $j$，那么第 $i+1$ 位的取值就有一定范围。例如在 $\{a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7},a_{8}\}$ 中，若 $a_{4}=3$，则$a_{3}$的取值范围为 $4-4$，$a_{1}$ 与 $a_{2}$ 的取值范围为 $1-2$，$a_{5},a_{6},a_{7},a_{8}$ 的取值范围为 $5-8$。

至于怎么求出取值范围，结合代码以及注释理解更佳。

转移就很好写了：

$$dp_{i,j}\longrightarrow dp_{i+1,p}(p\in [l_{i,j},r_{i,j}]) $$

其中 $[l_{i,j},r_{i,j}]$ 表示在第 $i$ 位编号为 $j$ 的情况下下一位的取值范围。

时间复杂度 $O(2^{2K}K)$。

::::info[时间复杂度证明] 自己证。

结合代码，发现复杂度主要分为两部分：

1. 求取值范围：求取值范围时每次扩大一倍，故为 $O(\log_{2}{2^K})$，即 $O(K)$。在乘上外层循环即为 $O(2^{2K}K)$。
2. 转移：$$\sum_{i=0}^{2^K-1} 2^K(r_{i,j}-l_{i,j}+1)=2^K\sum_{i=0}^{2^K-1} (r_{i,j}-l_{i,j}+1)$$
   手推一下，发现有 $\frac{1}{2}$ 的位置取值范围大小为 $1$，有 $\frac{1}{4}$ 的位置取值范围大小为 $2$……有 $\frac{1}{2^K}$ 的位置取值范围大小为 $2^{K-1}$，还有第一个点的取值范围大小为 $0$。
   所以 $$2^K\sum_{i=0}^{2^K-1} (r_{i,j}-l_{i,j}+1)=2^K\sum_{i=1}^{K} 2^K\frac{1}{2^i}2^{i-1} =2^KK2^{K-1}=2^{2K-1}K$$
   转移时间复杂度为 $O(2^{2K-1}K)$。

相加得总复杂度为 $O(2^{2K}K)$。 ::::

代码

跑的还是蛮快的。

#include<bits/stdc++.h>
using namespace std;
int k,a[515][515];
int dp[515][515];
int main()
{
	scanf("%d",&k);
	k=(1<<k);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			scanf("%d",&a[i][j]);
	memset(dp,127,sizeof(dp));
	for(int i=1;i<=k;i++) 
		dp[1][i]=0;
	for(int i=1;i<k;i++)
		for(int j=1;j<=k;j++)
		{
			int l=j,r=j; 
			int ll=i,rr=i;
			//表示[ll,rr]区间里每个数的取值范围均为[l,r](可能有部分数取值范围更小，但是不影响)
			//如果当前区间为第偶数个区间，那么可以知道其前面那个区间的范围
			//否则，可以知道后面那个区间的范围
			while((rr/((rr-ll+1)))%2==0) 
			{
				ll=rr-2*(rr-ll+1)+1;  //区间扩大一倍
				if((r/((r-l+1)))%2==0)	//同理
					l=r-2*(r-l+1)+1;
				else r=l+2*(r-l+1)-1;		
			}
			int yl=l,yr=r;//记录原先的l,r
			if((r/((r-l+1)))%2==0)					
			l=r-2*(r-l+1)+1,r=yl-1;
			else r=l+2*(r-l+1)-1,l=yr+1;
			for(int p=l;p<=r;p++)
			dp[i+1][p]=min(dp[i+1][p],dp[i][j]+a[j][p]);
		}
	int ans=1e9;
	for(int i=1;i<=k;i++)
		ans=min(ans,dp[k][i]);
	cout<<ans;
	return 0;
}