题面简述

一条线上等距地分布着

n

n

n 老鼠和

m

m

m 洞（

m

≥

n

m\geq n

m≥n），这连续

n

+

m

n+m

n+m 个位置上要么是老鼠要么是洞，一个老鼠进一个洞，代价是所有老鼠的路程和，问最小代价。

n

+

m

≤

5000

n+m\leq 5000

n+m≤5000

题解

平方做法

每个老鼠匹配一个洞，我们可以发现存在最优方案，使得路径两两之间不包含，这样一来，从左到右老鼠匹配的洞位置就是单增的。可以用调整法证明，如果两条路径包含，那么把终点位置互换，如果路径方向不同则更优（少了2×中间段长度），如果路径方向相同，根据绝对值算出来答案是相等的。

有了这个最优方案的特点后，我们就可以设计一个

D

P

\rm DP

DP ，令

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 表示前

i

i

i 个老鼠进前

j

j

j 个洞的最小代价，最终答案就是

d

p

[

n

]

[

m

]

dp[n][m]

dp[n][m]。不妨设

d

i

s

(

i

,

j

)

dis(i,j)

dis(i,j) 表示第

i

i

i 只老鼠进第

j

j

j 个洞的路径长度，状态转移如下：

d

p

[

i

]

[

j

]

=

min

⁡

{

d

p

[

i

]

[

j

−

1

]

,

d

p

[

i

−

1

]

[

j

−

1

]

+

d

i

s

(

i

,

j

)

}

dp[i][j]=\min\Big\{dp[i][j-1]~,~dp[i-1][j-1]+dis(i,j)\Big\}

dp[i][j]=min{dp[i][j−1] , dp[i−1][j−1]+dis(i,j)}

这应该很好理解，第

i

i

i 只鼠与第

j

j

j 个洞匹配，就是右边的式子，否则就是左边。

顺便提一下，有的做法是先推了一个

O

(

n

)

O(n)

O(n) 转移的

n

2

n^2

n2 DP，然后用前缀优化的，其实完全没这个必要。

然后，我们发现

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 的转移需要的两个前驱状态和它的曼哈顿距离挺小的 (

(

i

,

j

−

1

)

(i,j-1)

(i,j−1) 和

(

i

−

1

,

j

−

1

)

(i-1,j-1)

(i−1,j−1))，因此，我们用一两个小变量存一下

d

p

[

i

−

1

]

[

j

−

1

]

dp[i-1][j-1]

dp[i−1][j−1] ，能省掉第一维。由于数组访问的原理特性，你再卡卡常应该就能跑

30

m

s

\rm30~ms

30 ms 左右。

CODE

#include<set>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 5005

#define ENDL putchar('\n')

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int n,m,i,j,s,o,k;

int a[MAXN],b[MAXN],c[MAXN],cnb,cnc;

int Abs(int x) {return x < 0 ? -x:x;}

int dp[MAXN];

int main() {

	n = read();

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

		a[i] = read();

		if(a[i] == 1) b[++ cnb] = i;

		else c[++ cnc] = i;

	}

	for(int i = 1;i <= cnb;i ++) {

		int p = dp[0],pp; dp[0] = 0x3f3f3f3f;

		for(int j = 1;j <= cnc;j ++) {

			pp = dp[j]; dp[j] = min(dp[j-1],p + Abs(b[i]-c[j]));

			p = pp;

		}

	}

	printf("%d\n",dp[cnc]);

	return 0;

}

线性做法

我改过的题意简述是不是看起来很熟悉？

没错，这就是比较经典的模拟费用流板题。

与上面最主要的不同点是（我认为的）把绝对值符号拆开。

我们先换了一种

D

P

\rm DP

DP 方式，

d

p

[

i

]

[

j

]

dp[i][j]

dp[i][j] 表示前

i

i

i 个位置有

j

j

j 个洞需要匹配(

j

j

j 为负是表示有

−

j

-j

−j 个老鼠) ，已经匹配的路径和加上这

j

j

j 个洞(或

−

j

-j

−j 只鼠)的坐标和最大值。

其实是用了一点贪心的优化。由于路径不包含，所以前面不会同时有洞和老鼠向 i 后面连边。这样，DP 的转移就是决策唯一的了，这就不是 DP 而是类似递推了。因此用一些较复杂的标记可以把它优化成

O

(

n

)

O(n)

O(n)。

更详细的可以看上面的模拟费用流链接或是下面的

R

a

n

k

1

\rm Rank 1

Rank1 代码(30 ms)

CODE(Pyqe)

#include <bits/stdc++.h>

using namespace std;

long long n,ps[100069];

priority_queue<long long> pq;

int main()

{

	long long i,ii,k,z=0;

	scanf("%lld",&n);

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

	{

		scanf("%lld",&k);

		ps[i]=ps[i-1]+!k*2-1;

	}

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

	{

		k=min(max(ps[i],0ll),ps[n]);

		z+=abs(ps[i]-k);

		if(i-1)

		{

			z+=max(pq.top()-k,0ll);

		}

		for(ii=0;ii<2;ii++)

		{

			pq.push(k);

		}

		pq.pop();

	}

	printf("%lld\n",z);

}

[CF1525D] Armchairs （DP / 模拟费用流）的相关教程结束。