是去年写的了 存在笔记本里现在才发现（汗
过段时间会再补一些内容吧
兜兜转转还是你d(´ω｀*)
从一个奥妙重重的基本问题开始
给定(n)只老鼠，(m)个洞，求一个满足要求的匹配的代价。
Sub 1
限制：只能向左走 代价为距离
解法：直接排序 每个找左边空的最近的就行了
Sub 2
限制：无限制 (O(n))复杂度 代价为距离
解法：
dp方程(f[i][j])表示前(i)个位置 有(j)个洞要匹配 (j)可负（(-j)只老鼠等洞）
显然的想法是拆开距离 然后交叉匹配一定不优于不交叉匹配 所以我们把交叉匹配方式去掉
- 对于老鼠
- $jge 0, f[i][j]=f[i-1][j+1]+x[i] $
- (j<0, f[i][j] = f[i-1][j+1]-x[i]) （因为所有老鼠都必须进去 所以不需要决策）
- 对于洞
- (j>0 , f[i][j] = min(f[i-1][j-1] -y[i],f[i-1][j]))
- (jle 0, f[i][j] = f[i-1][j-1]+y[i])（(y[i])满足单调递增，所以必定直接转移最优）
这样转移是满的(O(n^2)) 考虑通过性质优化
对于洞的优化 对于决策(j>0)是 满足第一种转移更优 因为(y[i]>y[i-1]) 所以一定可以用(y[i])替换当时的转移从而变得更优【没匹配的左边的洞往右移动显然更优】 考虑到需要完全匹配 所以我们只用维护(f[i][0])就可以了 其余的一定是直接转移最优
由于所有转移都是直接转移 所以用两个栈维护最近的没匹配的鼠/洞 然后用tag维护全局加减就好啦
代码片段：
stack a,b;
int tag1=0,tag2=0,f0=0;
for(int i=1;i<=n;i++)
{
if(op[i]==1)//洞
{
tag1-=a[i],tag2+=a[i];
a.push(f0+a[i]-tag2);
f0=min(b.top()+tag1-a[i],f0);
b.pop();
}
else//鼠
{
tag1+=a[i],tag2-=a[i];
b.push(f0+a[i]-tag1);
f0=a.top()+tag2-a[i];
a.pop();
}
}
//我也没大搞懂（。
还有一种比较常见的(O(nlgn))做法
由于不存在交叉匹配 所以我们考虑贪心
我们维护以0为原点的差分数组 (d[i][j])
（(d[i][j]=f[i][j]-f[i][j-1],j>0; d[i][j]=f[i][j]-f[i][j+1] j<0)）
对于老鼠
(f[i][0]=f[i-1][0]+d[i-1][1]+a[i],d[i][j]=egin{cases}d[i-1][j+1] , j>0 || j<-1\ -d[i-1][1]-a[i] * 2 ,j=-1end{cases})
对于洞
(f[i][0]=min(f[i-1][0],f[i-1][0]+d[i-1][-1]+a[i]))
讨论(d[i-1][-1]+a[i])和(0)的关系
-
(d[i-1][-1]+a[i]<0)
(f[i][0]=f[i-1][0]+d[i-1][-1]+a[i],d[i][j]=egin{cases}d[i-1][j-1],j>1||j<0 \-d[i][-1]-a[i] imes 2 ,j=1end{cases})
-
(d[i-1][-1]+a[i]ge 0)
(f[i][0]=f[i-1][0],egin{cases}d[i-1][j-1],j>1||j<0 \-a[i] ,j=1end{cases})
发现这玩意是凸的 所以每次新添加的一定是最小的差分 直接用堆维护差分表
priority_queue<int> lf,rg; int f0=0;
for(int i=1;i<=n;i++)
{
if(op[i]==1)//洞
{
if(lf.top()+a[i]<0)
f0=f0+lf.top()+a[i], rg.push(-lf.top()-a[i]*2), lf.pop();
else rg.push(-a[i]);
}
else
f0=f0+rg.top()+a[i], lf.push(-rg.top()-a[i]*2), rg.pop();
}
还有一种思路就是堆里放的是可以后悔的 取出来可以反悔
Sub 3
限制：只能往左走 对于每个洞还有额外的代价(v[i])
解法：
按照(a_i)排序 然后维护洞的时候用(v_j-y_j)排序就好了 可能会有反悔的添加一个(-x_i)就好了
代码：戳我
Sub 4
限制：左右都可以走 每个洞有额外代价(v[i])
解法：
还是按照(a_i)（老鼠的(x_i)，洞的(y_i)）排序 遇到老鼠找一个代价最少的洞
我们按照费用流【最小权匹配】的思路走 我们先是贪心选 然后会遇到退流问题
-
老鼠(a)
必须匹配 所以从洞堆里拿出来一个配上对 然后再在鼠堆里填上反悔操作(-x[i]*2-w[j])（(w[j])表示匹配上的洞提供的代价）【其实是洞堆里添了一个(inf - x[i]*2) 因为鼠必须匹配 所以别的鼠来抢这个洞的时候这只鼠就无家可归了 所以其实就是非法匹配了
-
洞(a)
从老鼠堆里看最优的是否可以取
- 可以的话 权值加上(w[j]+x[i]+v[i]) 洞堆里添一个(-w[j]-2*x[i]) 鼠堆里添上一个(-x[i]-v[i])（因为鼠还是必须要有匹配的 而洞可以直接扔掉）
- 不可以的话 洞堆里添一个(-x[i]+v[i])
priority_queue<int> a,b; int f0;// a鼠堆 b洞堆 【小根堆
for(int i=1;i<=n;i++)
if(op[i]==1)// 洞
{
if(a.top()+x[i]+v[i]<0)
{
f0+=a.top()+x[i]+v[i];
b.push(-a.top()-2*x[i]);
a.pop();
a.push(-x[i]-v[i]);
}
else b.push(-x[i]+v[i]);
}
else
{
f0+=b.top()+x[i];
a.push(-b.top()-x[i]*2);
b.pop();
}
Sub 5
限制：分身术！每个洞其实有(c_i)的容量 每个位置叠了(d_i)只老鼠（均为(1e9)级别）
解法：
直接用pair记录流量（没 想 到 吧）
势能分析证出来是(O(nlgn))带常数【我要是会证我就是个茄子
题目：UOJ455 雪灾与外卖
代码：戳我
Sub 6
限制：上树
解法：
自底向上合并就好了 可并堆维护