洛谷1514 引水入城

Luogu

分析

一开始以为这是搜索题，然而事实证明这是搜索+DP/贪心。。。

首先不难想到，蓄水厂应建在第一行比两边都高的地方。因为如果不是这种地方，那么两侧一定可以给它供水，因此加上它的答案不会减少。

那么从这些高地开始floodfill，扩展出所有输水站可在地方，再计算出它能到达的最后一行的左右边界。
可以证得左右边界一定是连续的一段区间。因为如果存在中间分叉而导致区间不连续的情况，那么中间断掉的那些点就相当于被周围的比他低的点隔离，也就不存在其他的点可以更新它，就是无解的情况了。

那么这样我们就得到了第一行的每个点所能覆盖的区间。对应到最后一行，就成了区间覆盖问题

对于此题直接求最小覆盖数就好了。可以用贪心或DP。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int d[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
bool map[510][510]; //地图访问标记
bool vis[510]; //标记数组
int m,n,g[510][510]; //输入用
int L[510],R[510]; //左右端点
int f[510]; //DP用的
struct node //线段
{
    int L;
    int R;
}syc[510];
bool cmp(const node a,const node b) { return a.L<b.L; } //sort用
inline void DFS(int x,int y) //floodfill
{
    re int x1,y1;
    for (re int i=0;i<4;i++) //4个方向
    {
        x1=x+d[i][0];
        y1=y+d[i][1];
        if (x1>n||x1<=0||y1>m||y1<=0||g[x1][y1]>=g[x][y]) continue;
        if (map[x1][y1]) continue;
        map[x1][y1]=true; DFS(x1,y1);
    }
}
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline void write(int x) //输出优化
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
int main()
{
    n=read(); m=read();
    for (re int i=1;i<=n;i++)
         for (re int j=1;j<=m;j++)
             g[i][j]=read(); //输入
    for (re int i=1;i<=m;i++)
    {
        if (g[1][i]>=g[1][i-1]&&g[1][i]>=g[1][i+1]) //比两端高的（注意要加等号，否则会orz）
        {
            re int l=510,r=0;
            memset(map,0,sizeof(map)); //清空数组
            map[1][i]=true; DFS(1,i); //标记+floodfill
            for (re int j=1;j<=m;j++) //取左右边界
                 if (map[n][j])
                 {
                    vis[j]=true; //标记
                    if (!map[n][j-1]&&map[n][j]) l=j;
                    if (!map[n][j+1]&&map[n][j]) r=j;
                 }
            syc[i].L=l; syc[i].R=r;
        }
    }
    re int count=0; re bool fl=true;
    for (re int i=1;i<=m;i++)
        if (!vis[i]) //最后一行没有覆盖完
        {
            fl=false;
            count++;
        }
    if (!fl) //不能覆盖干旱区
    {
        write(0); putchar('\n');
        write(count); putchar('\n');
        return 0;
    }
    else
    {
        memset(f,127,sizeof(f));
        f[0]=0;
        sort(syc+1,syc+m+1,cmp); //排序
        for (re int i=1;i<=m;i++) //DP求值
             for (re int j=syc[i].L;j<=syc[i].R;j++)
                 f[j]=min(f[syc[i].L-1]+1,f[j]);
        write(1); putchar('\n');
        write(f[m]); putchar('\n');
    }
    return 0;
}