[CF1525D] Armchairs （DP / 模拟费用流）
题面简述
一条线上等距地分布着
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);
}
最新文章
- 2048游戏C语言代码
- Eclipse svn插件包
- ORACLE数据库删除表中记录报record is locked by another user
- js随机生成字母数字组合的字符串 随机动画数字
- HDU 5724 Chess （sg函数）
- mac在线恢复教程
- 【转】Java方向如何准备BAT技术面试答案(汇总版)
- html学习第一弹の常用标签的归类
- Linux中文件夹访问权限不足
- Python-递归、三元表达式列表生成式等
- 复旦大学2016--2017学年第一学期（16级）高等代数I期末考试第七大题解答
- Pyhon文件的用途
- C# 方法参数 out、ref、param 详解
- Python与矩阵论——特征值与特征向量
- Mysql初级第二天(wangyun)
- ofstream的使用方法--超级精细。C++文件写入、读出函数（转）
- Mac OS 10.12 - 在VMwear Workstation12.5.2中大写键和中英文输入法的切换！
- poj 1995 Raising Modulo Numbers 题解
- Android下点亮LED
- 《DSP using MATLAB》示例Example7.7