CF1525D 与 对 CF1525D 拓展题目的探究

题目链接：https://codeforces.com/contest/1525/problem/D

类似题目：

① Wannalfy 挑战赛7 Masha与老鼠：https://ac.nowcoder.com/acm/problem/14847

② UOJ【UER #8】雪灾与外卖：https://uoj.ac/problem/455

题目大意

有 n 个坐标 (1\to n) ，a[i] = 1 时表示该位置是老鼠，a[i]=0 时表示该位置是鼠洞。每只老鼠必须匹配一个鼠洞，并且代价是 |i-j| 。保证鼠洞的数目不少于老鼠的数目，求最小代价。

方法1：DP

复杂度 n^2

设 dp[i][j] 表示前 i 个老鼠匹配前 j 个鼠洞的最小代价。（先将老鼠和鼠洞的坐标分离）

（考场上要是有分离的意识，然后想到 dp 就好了。。。）

显然如果老鼠 i 和老鼠 j ，鼠洞 x ，鼠洞 y ，且 i<j ，x<y ，那么肯定是 i 匹配 x ，j 匹配 y 最优。

dp[0][u]=0

转移方程：

①：dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(a[i]-b[j]))

表示第 i 只鼠和第 j 只洞匹配，代价是坐标差。

②：dp[i][j]=min(dp[i][j],dp[i][j-1])

表示已经匹配了i只老鼠，跳过第 j 只鼠洞的代价。

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N],t1,dp[N][N],b[N],t2,n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);
        if(x) a[++t1]=i;
        else b[++t2]=i;
    }
    memset(dp,0x3f,sizeof dp);
    memset(dp[0],0,sizeof dp[0]);
    for(int i=1;i<=t1;++i){
        for(int j=1;j<=t2;++j){
            dp[i][j]=std::min(dp[i][j],dp[i-1][j-1]+abs(a[i]-b[j]));
            dp[i][j]=std::min(dp[i][j],dp[i][j-1]);
        }
    }
    printf("%d\n",dp[t1][t2]);
    return 0;
} 

方法2：DP

复杂度 n^2

不分离。

设 dp[i][j] 表示前 i 个坐标，老鼠的数量 – 鼠洞的数量 为 j 时的最小代价。

然后通过拆绝对值进行 dp

由于存在 j<0 的情况，所以我们在实现中给所有 j 加一个偏移量 n 。

#include<bits/stdc++.h>
const int N = 5010;
int n,f[N][N<<1],a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    f[0][n]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n<<1;++j){
            if(a[i]){
                if(j>=1){
                    if(j<=n)
                        f[i][j]=f[i-1][j-1]+i;
                    else
                        f[i][j]=f[i-1][j-1]-i;
                }
            }
            else{
                if(j<n)
                    f[i][j]=f[i-1][j+1]-i;
                else
                    f[i][j]=f[i-1][j+1]+i;
                if(j==n)
                    f[i][j]=std::min(f[i][j],f[i-1][j]);
            }
        }
    }
    printf("%d\n",f[n][n]);
    return 0;
}

方法3：方法二的优化 （ O(n) ）

可以发现方法二的 DP 有且仅有 j=0 时需要决策，其他位置都只是一个位移（从 j+1 或者 j-1 转移）

再整体加一个值（ i ）。

可以用两个栈（分为 j<0 和 j>0 来模拟这个转移的过程，j=0 单独计算，然后通过打标记来计算）

#include<bits/stdc++.h>
const int N = 5010;
int n,f[N][N<<1],a[N];
std::stack<int> L,R;
int covL,covR;
int zero = 0 ;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        if(a[i]){
            covL+=i;
            R.push(zero-covR);
            covR-=i;
            if(!L.empty())zero = L.top()+covL , L.pop();
            else zero=1e9;
        }
        else{
            covR+=i;
            if(zero!=1e9)
                L.push(zero-covL);
            covL-=i;
            if(!R.empty())
                zero=std::min(zero,R.top()+covR),R.pop();
        }
    }
    printf("%d\n",zero);
    return 0;
}

方法4：反悔型贪心

复杂度 O(nlogn)

开一个两个小根堆 H0,H1 。

H1 装 多余或者可能反悔的鼠洞的坐标以及代价

H0 装可能反悔的老鼠的代价

H1 装鼠洞，供老鼠进行反悔

H0 装老鼠，供鼠洞进行返回

什么是反悔，就是先选取老鼠 i 与鼠洞 j 进行匹配，代价为 w_1=abs(i-j) ，然后遇到了一个鼠洞 k ，现实是鼠洞 k 与 老鼠 i 匹配更好，但是我们已经贪心的将 i 和 j 匹配了，怎么办？

通过反悔型贪心，撤销过去的贪心操作。我们观察 w_2=k-i-w_1

w_2 表示将 k 和 i 进行匹配，撤销过去的操作的代价。

总代价 w_1+w_2=k-i ，就把第一次不合理的贪心撤销了。

然后具体题目具体分析，可以思考一下为什么要使用小根堆？

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 2e6 + 10;
int n,m;
priority_queue<ll,vector<ll>,greater<ll> > H0,H1;
ll ans = 0 ;
int a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        if(a[i]){
            ll w = 1e15;  // 如果暂时没有，就假设有一个代价为 1e15 的鼠洞可供选择
                          // 因为撤销这个操作(反悔)的收益太大了(1e15)。
                          // 所以这个选择在鼠洞多了以后必然会被撤销
            if(!H1.empty()){
                ll x = H1.top() ;H1.pop(); //取出可反悔（或者多余的）鼠洞
                w = i+x;//计算代价
            }
            ans += w;
            H0.push(-i-w);//添加可供后续反悔的操作
        }
        else{
            if(!H0.empty()&&i+H0.top()<0){  //验证返回了是不是会使总代价减少？
                ll w = i + H0.top() ; H0.pop(); 
                ans += w ; 
                H1.push(-i-w);  
            }
            else{
                H1.push(-i);//否则装入H1
            }
        }
    }
    printf("%lld",ans);
    return 0;
}