P1514 solution

数据下载
题目链接

这道题目有两问:能否满足要求以及如何达到最优
第一问很好做,直接dfs即可
但是第二问如果直接dfs因复杂度太高会有几个点TLE,所以不能只用dfs,
观察题目,可以得到每一个点覆盖的城市都是连续的,因为每个城市的海拔一定要小于前一个。
如果这个点没有被覆盖到,那么这个点的海拔一定高于与他相邻的点,
所以我们可以根据这个性质来对其进行dp,但是因为这个图是可以向上走的,(样例1就说明了这一点)

2 5
9 1 5 4 3
8 7 6 1 2

9->8->7->6->5->4->3->2->1

所以不能直接dp,需要一边进行记忆化搜索一边dp,
设置两个数组l[i][j]r[i][j],分别表示点(i,j)能够到达的最左边和最右边的点,
然后在进行dfs的过程中对每个点的情况分别进行dp就好。
下面是AC代码(with note)

#include<iostream>
#include<cstring>
#define mmm 600
int a[mmm][mmm],l[mmm][mmm],r[mmm][mmm],vis[mmm][mmm];
using namespace std;
int xx[4]={-1,0,1,0};
int yy[4]={0,1,0,-1};
int n,m;
#define nx xx[i]+x
#define ny y+yy[i]
void dfs(int x,int y)
{
    vis[x][y]=1;//设为访问过
    for(int i=0;i<4;i++)
    {
        if(nx<1||nx>n||ny<1||ny>m)
        continue; 
        if(a[nx][ny]>=a[x][y])//越界,海拔比现在高都要忽略
        continue;
        if(vis[nx][ny]==0)//未访问过
        dfs(nx,ny);//继续深搜
        l[x][y]=min(l[x][y],l[nx][ny]);
        //将开始搜的点的最左和最右边能达到的值更新为现在的值
        r[x][y]=max(r[x][y],r[nx][ny]);
    }
}
int main()
{
    int flag=0,cnt=0;
    memset(l,0x3f,sizeof(l));//将l数组设为极大值
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    l[n][i]=r[n][i]=i;//初始化数组为自己
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    for(int i=1;i<=m;i++)
    if(!vis[1][i])
    dfs(1,i);//深搜
    for(int i=1;i<=m;i++)
    if(!vis[n][i])//如果有一个沙漠里的城市没水喝
    {
        flag=1;//标记变为1
        cnt++;//没水喝的城市++
    }
    if(flag)//如果有城市没水喝
    {
        cout<<"0"<<endl<<cnt;//输出0和数量
        return 0;
    }
    int left=1,mr=0;
    while(left<=m)//寻找可以覆盖当前区间的点
    {
        for(int i=1;i<=m;i++)
        if(l[1][i]<=left)
        mr=max(mr,r[1][i]);//更新右区间
        cnt++;//答案++
        left=mr+1;
        //将左端点设到目前覆盖最右点的右边以便继续寻找能覆盖现在未覆盖区间的点
    }
    cout<<"1"<<endl<<cnt;//输出答案
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注