>打破惨案
by s5_gan @ 2018-12-15 10:36:25
@[s5_gan](/space/show?uid=51234) 感谢拯救，成功AC，此贴终结
by SkyLiYu @ 2018-12-15 10:40:44
@[隔壁小邱](/space/show?uid=22539) 不能用贪心覆盖。。。这点要注意qwq
by Arisu_Rivaille @ 2018-12-15 10:41:08
尴尬，请无视
by Arisu_Rivaille @ 2018-12-15 10:42:43
@[Arisu_Rivaille](/space/show?uid=152468) 这题贪心覆盖明显能做吧
by SkyLiYu @ 2018-12-15 11:15:32
@[隔壁小邱](/space/show?uid=22539) 好像不能是简单的贪心覆盖。。即不能是能选则选。。可能我没认真看您的代码吧
by Arisu_Rivaille @ 2018-12-16 22:06:28
@[隔壁小邱](/space/show?uid=22539) 我也是50分....
错的组输出的数都和你提交记录一样...
求助orz
```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 9999999
using namespace std;
int n,m,cunt,ans,sum[505];
int next[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
struct note {
int left=INF,right=-INF;
} cover[505];
struct node {
int left=INF,right=-INF,vis,h;
} mp[505][505];
bool cmp(note a,note b) {
return a.left<b.left;
}
void dfs(int x,int y) {
mp[x][y].vis=1;
if(x==n && y>=1 && y<=m) {
mp[x][y].left=min(y,mp[x][y].left);
mp[x][y].right=max(y,mp[x][y].right);
sum[y]=1;
}
for(int k=0; k<4; k++) {
int tx=x+next[k][0];
int ty=y+next[k][1];
if(mp[tx][ty].h<mp[x][y].h && tx>=1 && ty>=1 && tx<=n && ty<=m) {
if(!mp[tx][ty].vis) {
dfs(tx,ty);
}
mp[x][y].left=min(mp[x][y].left,mp[tx][ty].left);
mp[x][y].right=max(mp[x][y].right,mp[tx][ty].right);
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>mp[i][j].h;
}
}
for(int i=1; i<=m; i++) {
dfs(1,i);
}
for(int i=1; i<=m; i++) {
cover[i].left=mp[1][i].left;
cover[i].right=mp[1][i].right;
}
sort(cover+1,cover+m+1,cmp);
for(int i=1; i<=m; i++) {
if(!sum[i]) {
ans++;
}
}
if(ans) {
cout<<0<<endl;
cout<<ans;
return 0;
}
ans=0;
//区间覆盖
int last=1 ,far=0;
for(int i=1; i<=m; i++) {
far=max(far,cover[i].right);
if(cover[i+1].left>last) {
ans++;
last=far;
}
if(last>=m) {
cout<<1<<endl;
cout<<ans;
return 0;
}
}
}
```
by danefishhh @ 2019-01-27 12:30:34
@[danefishhh](/space/show?uid=54673) 这帖子已经很久了，我已经不记得当初为什么错了
by SkyLiYu @ 2019-01-27 12:52:30
@[隔壁小邱](/space/show?uid=22539)
还是谢谢你 ..已经过了..应该是最后区间覆盖有错，我一直以为是dfs的毛病..最后改dp过的
by danefishhh @ 2019-01-27 12:59:14