文档章节

NOIP2010引水入城题解

机智的帝江
 机智的帝江
发布于 2016/10/30 08:01
字数 539
阅读 6
收藏 0

首先这道题考验的并不是代码能力而是细心程度。仔细读题,你会发现对于每一个城市,如果要建水利设施,必须存在一个与它有公共边的比它高的城市才可以。运用贪心的算法,每次选取最高的靠近湖泊的城市进行搜索,当所有的干旱城市都建有水利设施的时候停止。当所有的靠近湖泊城市都建造了输水站而还有干旱城市没有满足条件时,需要for一遍干旱城市输出多少个没有建造水利设施。 那么接下来我们来证明一下贪心的正确性。 输入图片说明 如上图。当干旱城市需要建造水利设施时一定存在一个有公共边的比它海拔高的城市。那么当从最高点开始搜索时,保证最少能覆盖一个靠近湖泊的城市,从而减少>=1个输水站的建造。 代码如下

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
struct factory{
     long l,r;
}p[501];

long n,m,map[501][501],f[501],cnt=0;

bool vis[501][501]={0},ans[501]={0};


bool comp(const factory &a,const factory &b)
{
    return a.l<b.l;
}

void dfs(long x,long y,long ori)
{
     vis[x][y]=1;
     if(x==m){
          ans[y]=1;
          p[ori].l=min(p[ori].l,y);
          p[ori].r=max(p[ori].r,y);
     }
     if(map[x+1][y]<map[x][y]&&x!=m&&!vis[x+1][y])dfs(x+1,y,ori);
     if(map[x-1][y]<map[x][y]&&x!=1&&!vis[x-1][y])dfs(x-1,y,ori);
     if(map[x][y+1]<map[x][y]&&y!=n&&!vis[x][y+1])dfs(x,y+1,ori);
     if(map[x][y-1]<map[x][y]&&y!=1&&!vis[x][y-1])dfs(x,y-1,ori);
}

int main()
{
     cin>>m>>n;
     for(long i=1;i<=n;++i)p[i].l=f[i]=30000;
     f[0]=0;
     for(long i=1;i<=m;++i)
          for(long j=1;j<=n;++j)cin>>map[i][j];
     for(long i=1;i<=n;++i){
          dfs(1,i,i);
          memset(vis,0,sizeof(vis));
     }
     for(long i=1;i<=n;++i)
          if(!ans[i])++cnt;
     if(cnt)cout<<0<<endl<<cnt;
     else{
          cout<<1<<endl;
          for(long i=1;i<=n;++i)
               for(long j=1;j<=n;++j){
                    if(i>=p[j].l&&i<=p[j].r)f[i]=min(f[i],f[p[j].l-1]+1);
              }
     cout<<f[n];
     }
     return 0;
}

© 著作权归作者所有

上一篇: 虫食算
下一篇: 我是讨论版
机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
算法题--无重复字符的最长子串

题目描述 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: "...

独孤求媛
10/10
0
0
python数据挖掘系列教程——优化(独立变量优化)

全栈工程师开发手册 (作者:栾鹏) python数据挖掘系列教程 今天来学习变量优化问题。寻找使成本函数最小的题解。适用于题解相互独立的情况,设计随机优化算法、爬山法、模拟退火算法、遗传...

luanpeng825485697
2017/12/10
0
0
【日更】矩阵方面的各种习题?

恩……大二小萌新。 老板说要开始系统的学算法了呢恩……。 我先把之前开的矩阵习题做完再说别的好了。 然后后面可能会有一些最近刚出的题……2017年的icpc什么的。 打算停止更新啦……需要用...

s_amsara
2017/11/06
0
0
The 2018 ACM-ICPC Chinese Collegiate Programming Contest(Ningxia) 部分题解即AC代码

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/Adolphrocs/article/details/97617596 The 2018 ACM-ICPC Chinese Co...

Adolphrocs
08/31
0
0
BZOJ4519: [Cqoi2016]不同的最小割(Gomory–Hu 树)

传送门 题解: 两两之间的最小割等价于在Gomory–Hu 树上的最短边,同时告诉我们最小割最多只能有n-1种。 我们把Gomory–Hu 树建出来即可。 Wiki:Gomory–Hu Tree 题解:...

qq_35649707
2018/05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
4
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部