『动态规划·差分』队列

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

首先考虑第一小问，问题转化为：

• 每一行的问题互相独立。
• 令$c_j=a_{i,j}-a_{1,j}$，求将所有 $c_j$ 变成一个数字的方案数。

考虑第二小问，问题转化为：

• 固定每一列的第一个数字，并且保证这个数大于零且单调递增的情况下，将每一列的$c_i$固定成一个数字。
• 我们考虑DP来限制：设$f_{i,j}$ 表示前 $i$ 列 $a_{1,j}-a_{1,1}=j$时，花费的最小值。则有：
  $$f_{i,j}=f_{i-1,k}+val(\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{w}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{e})$$
  至于代价，我们只需要对差分序列求解中间的转折点，用前缀和的形式求解即可。其中该状态方程也用前缀$\min$ 的方式优化即可。
• 时间复杂度：$O(nV\log n)$

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>

using namespace std;
const int N = 2100;

int n, m;
int a[N][N], b[N], c1[N];
int f[N][N], g[N][N], c[N];

int read(void)
{
	int s = 0, w = 0; char c = getchar();
	while (!isdigit(c)) w |= c == '-', c = getchar();
	while (isdigit(c)) s = s*10+c-48, c = getchar();
	return w ? -s : s;
}

void work1(void)
{
	long long res = 0;
	for (int i=2;i<=m;++i)
		if (a[1][i] <= a[1][i-1]) return puts("-1"), void();
	for (int i=2;i<=n;++i)
	{
		for (int j=1;j<=m;++j) b[j] = a[i][j] - a[1][j];
		sort(b+1, b+m+1);
		int mid = b[m/2+1];
		for (int i=1;i<=m;++i) res += 1LL * abs(mid - b[i]); 
	}
	cout << res << endl;
	return ;
}

void work2(void)
{
	for (int i=0;i<=max(n,m);++i)
		for (int j=0;j<=2000;++j)
			f[i][j] = g[i][j] = 1e9;
	f[1][0] = 0;
	for (int j=0;j<=2000;++j) g[1][j] = 0;
	for (int i=2;i<=m;++i)
	{
		for (int j=1;j<=n;j++)
		  c[j]=a[j][i]-a[j][1];
		sort(c+1,c+n+1);
		for (int j=1;j<=n;j++)
		  c1[j]=c1[j-1]+c[j];
		for (int j=1;j<=2000;++j)
		{
			int w = 0, k;
			if (c[n] <= j) k = n; 
			else k = upper_bound(c+1, c+n+1, j) - c - 1;
			w = j * k - c1[k] + c1[n] - c1[k] - j * (n - k);
			f[i][j] = g[i-1][j-1] + w;
			g[i][j] = min(g[i][j-1], f[i][j]);
		}
	}
	cout << g[m][2000] << endl;
	return;
}

int main(void)
{
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	n = read(), m = read();
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) 
			a[i][j] = read();
	work1();
	work2();
	return 0;
}