题解：P11116 [ROI 2024] 割草 (Day 2)

· · 题解

被黄题硬控两天半（虽然在集训吧）。不过是道好题。

讲一下做这题的心路历程，看到有很多部分分决定先思考子任务 2 和 4。结果 inf 年后发现无解都没判对 / gg。看了一眼题解发现全都是神秘的贪心结论，于是继续大力画图后推了 dp 式子最终 AC。和题解区做法暂时没有重复所以来写一篇。

Solve

题意很明确就不过多赘述了。

这里我们首先注意到要覆盖整段草坪，任意两台机器人之间的部分不能留空 —— 它们合力一定要把中间的“缝隙” 切掉。

令 dp_{i,j} 表示已经处理了前 i 台机器人的方向，且第 i 台最终方向为 j（0 表示向左，1 表示向右）时所需的最小代价。最终答案就是 \min(dp_{n,0},dp_{n,1})。

考虑如何转移。假设我们已经算出了 dp_{i-1,0} 和 dp_{i-1,1}，要推 dp_{i,0} 和 dp_{i,1}。关键在于 \Delta=x_i-x_{i-1} 这段草必须被它们合力切掉。我们讨论「上一辆跑向哪个方向」和「当前这辆跑向哪个方向」的四种情况，合法的就转移。

前一辆 i-1 当前 i 可行性条件 说明
向右 向右 p_{i-1} \ge \Delta 前一辆要跑得远一点，至少切到或越过 x_i，才能衔接得上这一辆。
向左 向左 p_i \ge \Delta 当前这辆要能跑到或越过 x_{i-1}，才能和前面这辆左切的部分接上。
向右 向左 p_{i-1} + p_i \ge \Delta 它俩相向而行，分别切一段前缀和一段后缀，两段相加至少整个空隙。
向左 向右 不合法 它俩相反方向行驶，必定在它们中间留下空草坪，无法覆盖。

细节见代码。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9;
int n,x[N],p[N],d[N];
int f(int i,int s){//把状态 0/1 映射到方向 -1/+1 
    int w=(s==0?-1:1);
    return w==d[i]?0:1;
}
int dp[N][2],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>x[i]>>p[i]>>d[i];
    dp[1][0]=f(1,0);
    dp[1][1]=f(1,1);
    for(int i=2;i<=n;++i){
        dp[i][0]=dp[i][1]=INF;//初始化 
        int diff=x[i]-x[i-1];
        //右->右 
        if(p[i-1]>=diff && dp[i-1][1]<INF)
            dp[i][1]=min(dp[i][1],dp[i-1][1]+f(i,1));
        //左->左  
        if(p[i]>=diff && dp[i-1][0]<INF)
            dp[i][0]=min(dp[i][0],dp[i-1][0]+f(i,0));
        //右->左 
        if(p[i-1]+p[i]>=diff && dp[i-1][1]<INF)
            dp[i][0]=min(dp[i][0],dp[i-1][1]+f(i,0));
        //左->右 不合法 
    }
    ans=min(dp[n][0],dp[n][1]);
    cout<<(ans>=INF?-1:ans);//INF无解 
    return 0;
}

完结撒花