题目
点这里看题目。
分析
首先我们可以发现行列是独立的，因此可以分开计算，因此以下以行为例讲解。
设 \(H=\max_{i,j}h_{i,j}\)，\(\delta_i\) 为第 \(i\) 行增加的高度。那么，如果第 \(i\) 行和第 \(i+1\) 行之间有贡献，则必然有 \(|\delta_i-\delta_{i+1}|\le H\)；否则差值无论多少都可以。
注意到，当差值无论多少都可以的时候，我们可以直接从那个位置破环为链。剩下的相邻行的差值可以任意选取，因此这是一个可以简单贪心的问题。
考虑任意相邻行的差值绝对值都 \(\le H\) 的情况。这个时候必然满足差值的代数和为 0，可以 DP。如果暴力 DP 会得到 \(O(n^2H^2)\) 的算法，而注意到贡献可以和行分开，加入随机化即可将复杂度降到 \(O(nkH^2)\)，其中 \(k\) 是一个较小的常数，用于限制转移的状态。
小结：
-
思考的时候要更全面，“没有贡献时差值随意”没有想到，思维有点局限了。
-
多尝试几个方向，不要吊死在一种思路上。考试的时候只想到了“有一行的 \(\delta=0\)”，但是没有想到 \(\delta\) 差值的和为 0。使用前者解决问题会复杂得多，还是思考的时候太鲁莽了。
代码
#include <ctime>
#include <cstdio>
#include <random>
#include <algorithm>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int INF = 0x3f3f3f3f;
const int MAXN = 55, MAXH = 505, MAXV = 25005;
template<typename _T>
void read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
void write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b ) {
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b ) {
return a < b ? a : b;
}
int dp[2][MAXV << 1];
int seq[MAXN];
int row[MAXN][MAXH << 1], col[MAXN][MAXH << 1];
int A[MAXN][MAXN];
int N, M;
inline void Upt( int &x, const int v ) { x = MAX( x, v ); }
unsigned GetSeed() { char *tmp = new char; return time( 0 ) * ( unsigned long long ) tmp; }
int main() {
static std :: mt19937 rng( GetSeed() );
int mxH = 0;
read( N ), read( M );
rep( i, 1, N ) rep( j, 1, M )
read( A[i][j] ), mxH = MAX( mxH, A[i][j] );
rep( i, 1, N ) {
int j = i % N + 1;
rep( k, - mxH, mxH ) rep( q, 1, M )
row[j][k + mxH] += ( A[i][q] + k == A[j][q] );
}
rep( i, 1, M ) {
int j = i % M + 1;
rep( k, - mxH, mxH ) rep( q, 1, N )
col[j][k + mxH] += ( A[q][i] + k == A[q][j] );
}
int rMx = 0, cMx = 0;
int lim = 5 * mxH, pre, nxt, up, dn;
rep( i, 1, N ) {
int res = 0, tmp;
rep( j, 1, N ) if( i ^ j ) {
tmp = - INF;
rep( k, - mxH, mxH )
tmp = MAX( tmp, row[j][k + mxH] );
res += tmp;
}
rMx = MAX( rMx, res );
}
pre = 1, nxt = 0;
rep( i, 1, N ) seq[i] = i;
std :: shuffle( seq + 1, seq + 1 + N, rng );
rep( j, - lim, lim ) dp[nxt][j + lim] = - INF;
dp[nxt][lim] = 0;
rep( i, 1, N ) {
pre ^= 1, nxt ^= 1;
rep( j, - lim, lim )
dp[nxt][j + lim] = - INF;
rep( j, - lim, lim )
if( dp[pre][j + lim] >= 0 ) {
up = MIN( lim, j + mxH );
dn = MAX( - lim, j - mxH );
rep( k, dn, up )
Upt( dp[nxt][k + lim], dp[pre][j + lim] + row[seq[i]][j - k + mxH] );
}
}
rMx = MAX( rMx, dp[nxt][lim] );
rep( i, 1, M ) {
int res = 0, tmp;
rep( j, 1, M ) if( i ^ j ) {
tmp = - INF;
rep( k, - mxH, mxH )
tmp = MAX( tmp, col[j][k + mxH] );
res += tmp;
}
cMx = MAX( cMx, res );
}
pre = 1, nxt = 0;
rep( i, 1, M ) seq[i] = i;
std :: shuffle( seq + 1, seq + 1 + M, rng );
rep( j, - lim, lim ) dp[nxt][j + lim] = - INF;
dp[nxt][lim] = 0;
rep( i, 1, M ) {
pre ^= 1, nxt ^= 1;
rep( j, - lim, lim )
dp[nxt][j + lim] = - INF;
rep( j, - lim, lim )
if( dp[pre][j + lim] >= 0 ) {
up = MIN( lim, j + mxH );
dn = MAX( - lim, j - mxH );
rep( k, dn, up )
Upt( dp[nxt][k + lim], dp[pre][j + lim] + col[seq[i]][j - k + mxH] );
}
}
cMx = MAX( cMx, dp[nxt][lim] );
write( rMx + cMx ), putchar( '\n' );
return 0;
}