Codeforces Round #531 (Div. 3) F. Elongated Matrix（状压DP）

F. Elongated Matrix

题目链接：https://codeforces.com/contest/1102/problem/F

题意：

给出一个n*m的矩阵，现在可以随意交换任意的两行，最后从上到下，从左到右形成一个序列s1,s2.....snm，满足对于任意相邻的两个数，它们差的绝对值的最大值为k。

现在问怎么交换行与行，可以使得最后的这个k最大。

题解：

人生中第一道状压dp~其实还是参考了这篇博客：https://blog.csdn.net/CSDNjiangshan/article/details/86239183?tdsourcetag=s_pctim_aiomsg

这篇博客思路已经说得很清楚了，我就说下注意的几点吧：

行和列的下标是从0开始的，这是为了适应二进制操作，结合代码想想就知道了，我一开始就是这里没注意；

还有就是n=1时的特判，代码不能很好地处理这种情况，这时横坐标是0，不是1....

其余的照着思路写就是了。

我还有一个谜之问题，就是我先枚举中间点，比后枚举中间点要慢200.300ms左右，不知道为什么，希望有大佬能帮我解答一下。

代码如下：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N =  , M = 1e4+;

int a[N][M];

int dp[N][N][<<N];

int n,m;

int dis[N][N],dis_next[N][N];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            scanf("%d",&a[i][j]);

    memset(dis,INF,sizeof(dis));

    memset(dis_next,INF,sizeof(dis_next));

    memset(dp,,sizeof(dp));

    for(int i=;i<n;i++){

        for(int j=;j<n;j++){

            if(i==j) continue ;

            for(int k=;k<m;k++) dis[i][j]=min(dis[i][j],abs(a[i][k]-a[j][k]));

            for(int k=;k<m-;k++) dis_next[i][j]=min(dis_next[i][j],abs(a[i][k+]-a[j][k]));

        }

    }

    int ans = ;

    if(n==){

        ans = INF;

        for(int i=;i<m-;i++) ans=min(ans,abs(a[][i]-a[][i+]));

        printf("%d",ans);

        return ;

    }

    for(int l=;l<n;l++) dp[l][l][<<l]=INF;

    for(int l=;l<(<<n);l++){

        for(int i=;i<n;i++){

            if((l>>i)&==) continue ;

            for(int j=;j<n;j++){

                if((l>>j)& || i==j) continue ;

                for(int k=;k<n;k++){

                    if((l>>j)&==) continue ;

                    int now = l|(<<j);

                    dp[i][j][now]=max(dp[i][j][now],min(dp[i][k][l],dis[k][j]));

                }

            }

        }

    }

    int now = (<<n)-;

    for(int i=;i<n;i++){

        for(int j=;j<n;j++){

            if(i==j) continue ;

            ans=max(ans,min(dp[i][j][now],dis_next[i][j]));

        }

    }

    printf("%d",ans);

    return ;

}

巴特西

Codeforces Round #531 (Div. 3) F. Elongated Matrix（状压DP）

最新文章

热门文章