P1545 [USACO04DEC] Dividing the Path G题解

· · 题解

题意概括

给出奶牛数量，草坪长度，喷水的范围（分别对应 n,l,a,b），求出最少的不相交区间覆盖整段线段。

题目分析

本人蒟蒻一枚，看到此题就想到暴力。
用我们教练的话来说：“暴力要有方法的暴力！”
于是我就想到了 dp。

具体该怎样实现呢？

首先定义一个标记数组，
暴力标记每只奶牛喜欢的草区。
我们想一想，如果一个喷洒器位于 x，
那么其能喷洒到的范围为 [x-y,x+y]（y ∈ [a,b]），
而题目要求求到最小的喷洒器数量。
即我们考虑 dp，
用 dp_x 表示位于 x 位置之前总共需要的最少的喷洒器数量。

那么 x 位置之前的范围又该怎么求呢？

我们固定 j 为右端点，易求出此喷洒器可以喷洒到的范围为 (x-j \times 2)。

接下来就是 dp 的实现了

对于每个 dp_x 而言，都可以由 dp_j 转化而来，易得出本题状态转移方程：

dp_x = \min(dp_x,dp_j+1)

这样整个题目我们就处理完了。
最后……

-1 的情况怎样判断

如果 dp_l 的值大于一个极大值（我的代码里使用 10^9），
那么就可以判断为无解，输出 -1。

最后附上AC代码

#include<bits/stdc++.h>
using namespace std;
int n,l,a,b,s,e,i,j,k;
int dp[1000005];// dp 数组 
bool flag[1000005];//标记数组 
int main(){
    memset(dp,0x3f,sizeof dp);
    scanf("%d %d %d %d",&n,&l,&a,&b);
    dp[0]=0;
    for(i=1;i<=n;i++){
        scanf("%d %d",&s,&e);
        for(j=s+1;j<=e-1;j++) flag[j]=1;//暴力标记 
    }
    for(i=2;i<=l;i+=2){//遍历偶数 
        if(flag[i]) continue;
        for(j=a;j<=b;j++){
            k=i-(j<<1);//以i为右端点，这个状态喷洒的范围 
            if(k<0) continue;//超出范围 
            dp[i]=min(dp[i],dp[k]+1); //取最小值 
        }
    }
    printf("%d",((dp[l]>1e9)?(-1):(dp[l])));
    return 0;
}
//完结撒花

万望管理员大大通过