P7587 [COCI 2012/2013 #1] MARS题解

· · 题解

[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;
}