锐客网

  1. 首页 > it技术 > >

Codeforces|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
这篇博客思路已经说得很清楚了，我就说下注意的几点吧：
【Codeforces|Codeforces Round #531 (Div. 3) F. Elongated Matrix（状压DP）】行和列的下标是从0开始的，这是为了适应二进制操作，结合代码想想就知道了，我一开始就是这里没注意；
还有就是n=1时的特判，代码不能很好地处理这种情况，这时横坐标是0，不是1....
其余的照着思路写就是了。
我还有一个谜之问题，就是我先枚举中间点，比后枚举中间点要慢200.300ms左右，不知道为什么，希望有大佬能帮我解答一下。

代码如下：

#include #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 16 , M = 1e4+5; int a[N][M]; int dp[N][N][1<>i)&1==0) continue ; for(int j=0; j>j)&1 || i==j) continue ; for(int k=0; k>j)&1==0) continue ; int now = l|(1<

转载于:https://www.cnblogs.com/heyuhhh/p/10252277.html

    推荐阅读


    上一篇：jquery ui（三）弹出窗口 dialog

    下一篇：21.Shiro在springboot与vue前后端分离项目里的session管理