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<jx<y ,那么肯定是 i 匹配 xj 匹配 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

8E6_RR7UU93J58JKRPL6A`T.png

#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<0j>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 匹配更好,但是我们已经贪心的将 ij 匹配了,怎么办?

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

w_2 表示将 ki 进行匹配,撤销过去的操作的代价。

总代价 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;
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注