noip 2010 引水入城 bfs+剪枝+dp

133 阅读 0 评论 88 点赞

我是靠谱客的博主危机龙猫，这篇文章主要介绍noip 2010 引水入城 bfs+剪枝+dp，现在分享给大家，希望可以做个参考。

从第一行每一个点开始bfs，这样可以知道每一个点可以覆盖在最后一行的区间。判一下不能覆盖的情况。然后可以完全覆盖的话，那么最优解中第一行的点所对应最后一行中一定是连续的一段。有两种证明方法：（1、显然法：显然它是对的。2、反证法：反正它是对的。）
假设i小于k小于j若a出发，能到i，j，却不能到k，那么从a到i的路径和从a到j的路径和旱区那条边围成的区域中必定有一道能把k封闭起来的“墙”既然k被封闭起来了，那么其他所有的湖泊点都不能到达k。
然后区间线段覆盖问题，可以贪心，可以DP；

复制代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
int a[505][505];
int use[505][505];
int cx[]={0,0,1,0,-1};
int cy[]={0,1,0,-1,0};
queue<int> q;
int n,m;
void bfs(int p)
{
q.push(1);q.push(p);
use[1][p]=p;
int x,y,u,v;
while(!q.empty())
{
x=q.front();q.pop();
y=q.front();q.pop();
for(int i=1;i<=4;i++)
{
u=x+cx[i];v=y+cy[i];
if(u>n||u<1||v>m||v<1)
continue;
if(use[u][v]!=p&&a[u][v]<a[x][y])
{
use[u][v]=p;
q.push(u);
q.push(v);
}
}
}
}
struct P{int l,r;}p[505];
P d[505];int tot;
bool cmp(P a,P b)
{
if(a.r!=b.r)
return a.r<b.r;
return a.l>b.l;
}
stack<int> S;
int dp[505];
int inf=1e9;
void read(int &a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
read(a[i][j]);
int h,l,r;
for(int i=1;i<=m;i++)
{
if(a[1][i]>=a[1][i+1]&&a[1][i]>=a[1][i-1])bfs(i);
h=0;l=600;r=0;
for(int j=1;j<=m+1;j++)
{
if(use[n][j]==i)
{
if(!h)l=j,r=j,h=1;
else r=j;
}
else if(h) break;
}
p[i].l=l;p[i].r=r;
}
int ans=0;
for(int i=1;i<=m;i++)
if(!use[n][i]) ans++;
if(ans)
{
puts("0");
printf("%d",ans);
}
else
{
sort(p+1,p+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(!S.empty())
{
int t=S.top();
while(p[i].l<=p[t].l)
{
S.pop();
if(S.empty())break;
t=S.top();
}
}
S.push(i);
}
tot=S.size();
int cnt=tot;
while(!S.empty())
{
d[tot]=p[S.top()];
S.pop();tot--;
}
ans=1e9;
for(int i=1;i<=m;i++)
dp[i]=inf;
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<i;j++)
if(d[i].l<=d[j].r+1)
dp[i]=min(dp[i],dp[j]+1);
if(d[i].r==m)
ans=min(ans,dp[i]);
}
puts("1");
printf("%d",ans);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
int a[505][505];
int use[505][505];
int cx[]={0,0,1,0,-1};
int cy[]={0,1,0,-1,0};
queue<int> q;
int n,m;
void bfs(int p)
{
q.push(1);q.push(p);
use[1][p]=p;
int x,y,u,v;
while(!q.empty())
{
x=q.front();q.pop();
y=q.front();q.pop();
for(int i=1;i<=4;i++)
{
u=x+cx[i];v=y+cy[i];
if(u>n||u<1||v>m||v<1)
continue;
if(use[u][v]!=p&&a[u][v]<a[x][y])
{
use[u][v]=p;
q.push(u);
q.push(v);
}
}
}
}
struct P{int l,r;}p[505];
P d[505];int tot;
bool cmp(P a,P b)
{
if(a.r!=b.r)
return a.r<b.r;
return a.l>b.l;
}
stack<int> S;
int dp[505];
int inf=1e9;
void read(int &a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
read(a[i][j]);
int h,l,r;
for(int i=1;i<=m;i++)
{
if(a[1][i]>=a[1][i+1]&&a[1][i]>=a[1][i-1])bfs(i);
h=0;l=600;r=0;
for(int j=1;j<=m+1;j++)
{
if(use[n][j]==i)
{
if(!h)l=j,r=j,h=1;
else r=j;
}
else if(h) break;
}
p[i].l=l;p[i].r=r;
}
int ans=0;
for(int i=1;i<=m;i++)
if(!use[n][i]) ans++;
if(ans)
{
puts("0");
printf("%d",ans);
}
else
{
sort(p+1,p+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(!S.empty())
{
int t=S.top();
while(p[i].l<=p[t].l)
{
S.pop();
if(S.empty())break;
t=S.top();
}
}
S.push(i);
}
tot=S.size();
int cnt=tot;
while(!S.empty())
{
d[tot]=p[S.top()];
S.pop();tot--;
}
ans=1e9;
for(int i=1;i<=m;i++)
dp[i]=inf;
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<i;j++)
if(d[i].l<=d[j].r+1)
dp[i]=min(dp[i],dp[j]+1);
if(d[i].r==m)
ans=min(ans,dp[i]);
}
puts("1");
printf("%d",ans);
}
return 0;
}