http://www.rqnoj.cn/problem/601
今天发现最小区间覆盖竟然是贪心,不用DP!于是我又找到这题出来撸了一发。
要找到最上面每个城市分别能覆盖最下面哪些城市,如果最下面有城市怎么都覆盖不到,就输出覆盖不到的城市数。
这样,最上面的城市能覆盖的最下面的城市一定是一个区间,不会从中间断开。因为如果断开了,那断开的这一部分怎么都没有水能流到了,可以按照覆盖不到处理。当全部能覆盖到的时候,才要用这些区间来算最小需要多少个起点城市,有覆盖不到的就不用这些区间了。居然,好像说得很复杂,就是有覆盖不到的点,记这些区间就没什么用,记错了也没关系;如果没有覆盖不到的点,这些区间就是对的。
这个部分我用q[i][j].l和q[i][j].r记录[i][j]点能达到的区间[l,r]。深搜,搜到底端节点就
q[x][y].l=min(q[x][y].l , y);
q[x][y].r=max(q[x][y].r , y);
can++;
can记录的是能到达的城市的数量,用来统计有没有城市到不了的。
因为如果(x,y)这个点能到的区间算好了之后,能到达(x,y)的点肯定包含这个区间,就不用再进入(x,y)点再算一遍区间了,直接加上这个区间就好。这样,每个点就只用进入一次。一下就能深搜完啦。
然后q[0][i].l和q[0][i].r就记录了第一行的i号节点能到的区间,接下来就是最小区间覆盖了。
以前我用的是DP,f[i]记录从(n,1)到(n,i)这个区间所需要的最少起点城市数。
f[]:=;
for i:= to m do{从[1,1]区间开始,到[1,2]区间,不断延伸,直到[1,m]区间}
begin
f[i]:=;
for j:= to m do
if (e[,j].l<=i)and(e[,j].r>=i)then
f[i]:=min(f[i],f[e[,j].l-]+);
end;
这是pascal代码,碉不碉。
然后我今天看到最小区间覆盖竟然是贪心…
每次找到包含起始节点s(这题里是0)的r最大的区间,加入结果区间里,然后s=r+1,重复直到s>=m,就覆盖完了…
AC代码:
#include<iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 555
#define RE freopen("in.txt","r",stdin); using namespace std; const int dx[]= {,,-,};
const int dy[]= {-,,,};
const int inf=; struct Qujian
{
int l,r;
}; bool cmp(Qujian x,Qujian y)
{
return x.r>y.r;
} int n,m,can;
int a[MAXN][MAXN];
Qujian q[MAXN][MAXN];
bool w[MAXN][MAXN]; int farm();
void init(); int main()
{
//RE
while(scanf("%d%d",&n,&m)!=EOF)
{
farm();
}
return ;
} void dfs(int x,int y)
{
int i,j,nx,ny;
if(w[x][y]) return;
w[x][y]=true;
if(x==n-)
{
q[x][y].l=min(q[x][y].l , y);
q[x][y].r=max(q[x][y].r , y);
can++;
}
for(i=; i<; i++)
{
nx=x+dx[i];
ny=y+dy[i];
if(nx< || ny< || nx>=n || ny>=m) continue;
if(a[nx][ny]>=a[x][y]) continue;
if(!w[nx][ny]) dfs(nx,ny);
q[x][y].l=min(q[x][y].l , q[nx][ny].l);
q[x][y].r=max(q[x][y].r , q[nx][ny].r);
}
} int farm()
{
int i,j;
init();
for(i=; i<n; i++)
for(j=; j<m; j++)
{
scanf("%d",&a[i][j]);
}
for(i=; i<m; i++)
dfs(,i);
// for(i=0; i<n; i++)
// {
// for(j=0; j<m; j++)
// cout<<'['<<q[i][j].l<<','<<q[i][j].r<<"] ";
// cout<<endl;
// }
if(can<m)
{
printf("0\n%d\n",m-can);
}
else
{
sort(q[],q[]+m,cmp);
i=;
int ans=;
while(i<m)
{
for(j=; j<m; j++)
if(q[][j].l<=i)
{
i=q[][j].r+;
ans++;
break;
}
}
printf("1\n%d\n",ans);
} return ;
} void init()
{
int i,j;
memset(q,,sizeof(q));
can=;
for(i=; i<n; i++)
for(j=; j<m; j++)
q[i][j].l=inf;
memset(w,false,sizeof(w));
}
NOIP2010 引水入城 题解的更多相关文章
-
521. [NOIP2010] 引水入城 cogs
521. [NOIP2010] 引水入城 ★★★ 输入文件:flow.in 输出文件:flow.out 简单对比时间限制:1 s 内存限制:128 MB 在一个遥远的国度,一侧是风景秀 ...
-
luoguP1514 引水入城 题解(NOIP2010)(Bfs+贪心)
P1514 引水入城 题目 #include<iostream> #include<cstdlib> #include<cstdio> #include<c ...
-
NOIP2010 引水入城
4引水入城 题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠.该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个 ...
-
题解【洛谷P1514】[NOIP2010]引水入城
题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠.该国的行政区划十分特殊,刚好构成一个 \(N\) 行 \(M\) 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市 ...
-
[NOIP2010] 引水入城 贪心 + 记忆化搜索
---题面--- 题解: 本蒟蒻并没有想到bfs的做法,,,, 只会dfs了 首先我们需要知道一个性质. 我们设k[i].l 为在i点建立水库可以支援到的最左边的城市,k[i].r为最右边的. 那么点 ...
-
NOIP2010引水入城[BFS DFS 贪心]
题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠.该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度. ...
-
noip2010 引水入城 bfs+贪心
如果能够实现,每个河边的城市对应的控制区域一定是一条线段. 所以直接bfs每个河边的城市,贪心线段的右端点 #include<cstdio> #include<cstring> ...
-
Luogu1514 NOIP2010 引水入城 BFS、贪心
传送门 NOIP的题目都难以写精简题意 考虑最上面一排的某一个点对最下面一排的影响是什么样的,不难发现必须要是一段连续区间才能够符合题意. 如果不是一段连续区间,意味着中间某一段没有被覆盖的部分比周围 ...
-
luogu1514 [NOIp2010]引水入城 (bfs+记忆化搜索)
我们先bfs一下看看是否能到最底下的所有点 如果不能的话,直接把不能到的那几个数一数就行了 如果能的话: 可以发现(并不可以)某格能到达的最底下的格子一定是一个连续的区间 (因为如果不连续的话,我们先 ...
随机推荐
-
GithubPage 的简单使用
这是我第一次写博客,主要是记录自己前端学习的经历.这次写一下GitHubpage 的简单使用.我用这里并没有想挂博客,主要是挂自己的一些小作品应用到简历中. 第一步: 首先先注册Github账号,创建 ...
-
proxmox3.2安装FreeBSD或者FreeNAS注意事项
别的不多说了,白般尝试,终于安装成功,原来硬件要如下设置才行,如下: 1)内存要开大点,512M 800M都不行,最后开导2G才可以,如下: 2)kvm硬件虚拟化一定要选择“否”,默认是“是”,这里 ...
-
SOCKET 地址
地址格式: 函数bind和getsockname使用通用数据类型:struct sockaddr*来指向socket地址. #incude <sys/socket.h> struct so ...
-
NC表型参照类
package nc.ui.bd.ref; /** * 表参照-其他参照基类. 创建日期:(2001-8-23 20:26:54) 模型里未处理栏目 * * @author:张扬 * */ impor ...
-
C语言选择法排序
#include <stdio.h> int main() { int i, j, p, n, q; ] = {, , , , }; //对无序数组进行排序 ; i<; i++) { ...
-
阿里云ECS-Nginx阿里云客户端IP日志记录
#前端有SLB服务,记录客户端真实IP信息 log_format main 'realip:$http_x_forwarded_for slbip:$remote_addr-$remote_user ...
-
org/eclipse/jetty/server/Handler : Unsupported major.minor version 52.0
注:本文来源于<org/eclipse/jetty/server/Handler : Unsupported major.minor version 52.0> Exception in ...
-
C# PDF转Image图片
概述 PDF是常用的文件格式之一,通常情况下,我们可以使用itextsharp生产PDF文件:可是如何将PDF文件转换成图片那?目前常用的: 思路1.根据PDF绘画轨迹重新绘制图片: 思路2.是将PD ...
-
在 Windows 8、Windows 10 桌面模式下的 .NET Framework 程序中,引用 Windows.Runtime 的 API。
参考:1.https://www.cnblogs.com/webtojs/p/9675956.html 2.http://jennal.com/2016/04/28/using-windows-run ...
-
easyui datagrid remoteSort的实现 Controllers编写动态的Lambda表达式 IQueryable OrderBy扩展
EF 结合easy-ui datagrid 实现页面端排序 EF动态编写排序Lambda表达式 1.前端页面 var mainListHeight = $(window).height() - 20; ...