「Codeforces 1102F」Elongated Matrix

发表于 | | 阅读次数:
字数统计: 852 字

Description

题目链接：Codeforces 1102F

给你一个 $n​$ 行 $m​$ 列的矩阵 $a_{i,j}​$，其中每个元素都是正整数 。

你可以任意改变行的顺序，但是不能改变同一行中元素的顺序。确定行的顺序后，你可以通过以下方式遍历整个矩阵：首先访问从顶行到底部的第一列的所有元素，然后对第二列进行相同的操作，依此类推。在遍历期间，按照访问它们的顺序记下元素，得到一个序列 $s_i​$。设这个序列为 $s_1,s_2,\dots,s_{nm}​$。

如果对于任意的 $i(1\le i<nm)​$，有 $\vert s_i-s_{i+1}\vert\ge k​$ 成立，我们称 $k​$ 是合法的。

你要做的是寻找一个 $a_{i,j}$ 的行的排列顺序，使得最大的合法的 $k​$ 值最大。

数据范围：$1\le n\le 16​$，$1\le m\le 10^4​$，$2\le nm​$，$1\le a_{i,j}\le 10^9​$

Solution

我们发现行的排列顺序的本质是：哈密顿回路，即第 $i​$ 行接着第 $i+1​$ 行并产生贡献，第 $n​$ 行接着第 $1​$ 行并产生贡献。注意到 $n​$ 的范围很小，我们可以考虑状态压缩。

由于第一行（哈密顿回路中的起点）是不确定的，因此我们首先要枚举起点。定义状态 $f_{i,j}$ 表示已经考虑了 $i$ 集合内的行，最后一行是 $j$ 时，不考虑第一行和最后一行的贡献的最大贡献（要求 $\vert s_i-s_{i+1}\vert$ 的最小值最大）。其中第 $i$ 行和第 $j$ 的贡献是指：同一列的元素的的差的绝对值的最小值。

状态转移方程如下：

其中 $\text{cost}(i,j)​$ 表示第 $i​$ 行和第 $j​$ 行相邻的贡献。

统计答案时，我们枚举结束点 $i​$，根据起点 $k​$ 可以得到答案为：

其中 $2^n-1$ 为全集，$\text{cost}’(i,j)$ 表示第 $i$ 行为第一行，第 $j$ 行为最后一行时，第一行和最后一行之间的贡献。

时间复杂度：$O(2^nn^3)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=17,M=1e4+5;
const int INF=1<<30;
int n,m,a[N][M],f[1<<N][N],g[N][N],h[N][N];

void init() {
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) {
        g[i][j]=INF,h[i][j]=INF;
        for(int k=1;k<=m;++k) g[i][j]=std::min(g[i][j],std::abs(a[i][k]-a[j][k]));
        for(int k=2;k<=m;++k) h[i][j]=std::min(h[i][j],std::abs(a[i][k-1]-a[j][k]));
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i) for(int j=1;j<=m;++j) scanf("%d",&a[i][j]);
    init();
    int ans=0;
    for(int k=0;k<n;++k) {
        memset(f,0,sizeof(f));
        f[1<<k][k]=INF;
        for(int S=0;S<(1<<n);++S) for(int i=0;i<n;++i) if(S&(1<<i)) {
            for(int j=0;j<n;++j) {
                if(!(S&(1<<j))) f[S|(1<<j)][j]=std::max(f[S|(1<<j)][j],std::min(f[S][i],g[i][j]));
            }
        }
        for(int i=0;i<n;++i) {
            ans=std::max(ans,std::min(f[(1<<n)-1][i],h[k][i]));
        }
    }
    printf("%d\n",ans);
    return 0;
}
0%