华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1069|回复: 2
打印 上一主题 下一主题

P1514 引水入城

[复制链接]

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
跳转到指定楼层
楼主
发表于 2018-10-2 19:38:07 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目描述
在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行 ×M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。



为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此,只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。由于第N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

输入输出格式
输入格式:
每行两个数,之间用一个空格隔开。输入的第一行是两个正整数N,M,表示矩形的规模。接下来N 行,每行M 个正整数,依次代表每座城市的海拔高度。

输出格式:
两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。

输入输出样例
输入样例#1:
2 5
9 1 5 4 3
8 7 6 1 2
输出样例#1:
1
1
输入样例#2:
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
输出样例#2:
1
3
说明
【样例1 说明】

只需要在海拔为9的那座城市中建造蓄水厂,即可满足要求。

【样例2 说明】



上图中,在3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这3个蓄水厂为源头在干旱区中建造的输水站分别用3 种颜色标出。当然,建造方法可能不唯一。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

2

主题

19

帖子

114

积分

注册会员

Rank: 2

积分
114
推荐
发表于 2020-1-12 10:25:33 | 只看该作者
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dx[]={-1,0,1,0};
  4. int dy[]={0,1,0,-1};
  5. int mp[510][510],f[520],vis[510][510],ans,l[510][510],r[510][510],n,m;
  6. bool flag=1;
  7. void dfs(int x,int y)
  8. {
  9.    vis[x][y]=1;
  10.    for(int i=0;i<4;i++)
  11.    {
  12.        int x1=x+dx[i];
  13.        int y1=y+dy[i];
  14.        if(x1<1 || x1>n || y1<1 || y1>m || mp[x][y]<=mp[x1][y1]) continue;
  15.        if(!vis[x1][y1]) dfs(x1,y1);
  16.        l[x][y]=min(l[x][y], l[x1][y1]);
  17.        r[x][y]=max(r[x][y], r[x1][y1]);
  18.    }

  19. }
  20. int main()
  21. {
  22.     memset(l, 21000000, sizeof(l));
  23.     cin>>n>>m;
  24.     for(int i=1;i<=n;i++)
  25.         for(int j=1;j<=m;j++)
  26.         {cin>>mp[i][j];if (i==n) l[i][j]=r[i][j]=j;}
  27.     for(int i=1;i<=m;i++)
  28.         if(!vis[1][i])dfs(1,i);
  29.         for(int i=1;i<=m;i++)if(!vis[n][i]) {flag=0;ans++;}
  30.         if(!flag) {cout<<0<<endl<<ans<<endl;return 0;}
  31.         f[1]=1;
  32.     int left=1,right=r[1][1];
  33.      while (left<=m)
  34.     {
  35.         for(int i=1;i<=m;i++)
  36.         if (l[1][i]<=left)right=max(right, r[1][i]);
  37.         left=right+1;
  38.         ans++;
  39.     }
  40.     cout<<1<<endl<<ans<<endl;
  41.     return 0;
  42. }
复制代码
回复 支持 1 反对 0

使用道具 举报

0

主题

2

帖子

127

积分

注册会员

Rank: 2

积分
127
板凳
发表于 2020-1-12 15:33:03 | 只看该作者

#include<bits/stdc++.h>
using namespace std;
const int mm=501;
int n,m;
int l[mm],r[mm];
int mp[mm][mm];
bool bb[mm];
struct BFS
{
    int x,y;
}bfs[1000000];
int dr1[5]={0,0,0,1,-1};
int dr2[5]={0,1,-1,0,0};
bool check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m)
        return 1;
    else
        return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[j];

    ///BFS(找每个沿湖城市可覆盖的区间)
    int k=1;
    for(int i=1;i<=m;i++)
    {
        //cout<<i<<endl;
        int a=1,b=2;
        bool bo=0;
        int ll=520,rr=0;
        bfs[a].x=1;bfs[a].y=i;
        while(a<b)
        {
            int xx,yy;
            for(int j=1;j<=4;j++)
            {
                xx=bfs[a].x+dr1[j];
                yy=bfs[a].y+dr2[j];
                if(check(xx,yy)&&mp[bfs[a].x][bfs[a].y]>mp[xx][yy])
                {
                    bfs.x=xx;
                    bfs.y=yy;
                    b++;
                    if(xx==n)
                    {
                        bb[yy]=1;
                        if(yy>rr)
                        {
                            rr=yy;
                            bo=1;
                        }
                        if(yy<ll)
                        {
                            ll=yy;
                            bo=1;
                        }
                    }
                }
            }
            a++;
        }
        if(bo)
        {
            l[k]=ll;
            r[k]=rr;
            k++;
        }
    }
    k--;

    ///CHECK
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(bb==0)
        {
            ans++;
        }
    }
    if(ans>0)
    {
        cout<<0<<endl<<ans;
        return 0;
    }
    cout<<1<<endl;
    /*
    for(int i=1;i<=k;i++)
    {
        cout<<l<<' '<<r<<endl;
    }
    */

    ///DP
    int f[mm];
    f[1]=0;
    for(int i=2;i<=mm-1;i++)
        f=mm;
    for(int i=1;i<=k;i++)
    {
        int _min=mm;
        for(int j=l;j<r;j++)
        {
            if(f[j]<_min)
                _min=f[j];
        }
        if(l==1)
            f[r]=_min+1;
        else
            f[r]=min(f[r],_min+1);
    }
    cout<<f[m];

    return 0;
}
/*
3 5
9 1 5 4 3
8 4 3 3 4
2 3 5 4 3
*/
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-2 00:36 , Processed in 0.099007 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表