记忆化搜索以及最小线段覆盖 洛谷P1514

题目自行阅读洛谷

题解： 记忆化搜索就是搜索过的点不再搜索，而是在某个点搜索到它时将它记录的结果返回，这样便大大节约了时间。

最小线段覆盖即将left值先置为最左边，然后找到包含left这个点的最大右边界，之后更新left值为right+1，并重复上述过程，知道left大于右边界。

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f
using namespace std;
int n,m;
int l[505][505],r[505][505];
int high[505][505];
int vis[505][505];
int dx[]={
          
   0,0,-1,1};
int dy[]={
          
   -1,1,0,0};
void dfs(int x,int y)
{
          
   
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
          
   
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(0<xx&&xx<=n&&0<yy&&yy<=m&&high[x][y]>high[xx][yy])
        {
          
   
           // printf("%d
",high[xx][yy]);
            if(!vis[xx][yy])
                dfs(xx,yy);
            l[x][y]=min(l[xx][yy],l[x][y]);   //更新节点信息，记录结果
            r[x][y]=max(r[xx][yy],r[x][y]);   //这样搜索过的点就不会重复搜索
        }
    }
}
int main()
{
          
   
    cin>>n>>m;
    int flag=0;
    int cnt=0;
    memset(l,inf,sizeof(l));  //将l的值置为inf方面找出最小值
    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>>high[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;
            cnt++;
        }
    if(flag)
    {
          
   
        cout<<0<<endl;
        cout<<cnt<<endl;
    }
    else
    {
          
   
        cout<<1<<endl;
        int left=1;
        int right=0;
        cnt=0;
        while(left<=m)  //最小线段覆盖
        {
          
   
            //right=0;
            for(int i=1;i<=m;i++)   //通过不断加大left值找到最大right值直到完全覆盖
            {
          
   
                //printf("%d
",l[1][i]);
                if(l[1][i]<=left)
                {
          
   
                    right=max(right,r[1][i]);
                }
            }
            left=right+1;   //更新left值
            cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}