wa 了四个点 求助大佬

witw @ 2022-01-25 14:56:17

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
const int N=1005;
const int fx[4]={0,0,1,-1};
const int fy[4]={1,-1,0,0}; 
int f[N][N],a[N][N];
bool vis[N][N];
void dfs(int x,int y){
    for(int i=0;i<4;++i){
        int x1=x+fx[i],y1=y+fy[i];
        if(x1<=0||y1<=0||x1>n||y1>m||a[x][y]<a[x1][y1])continue;
        if(vis[x1][y1]){
            vis[x][y]=true;
            f[x][y]=max(f[x][y],f[x1][y1]+a[x][y]-a[x1][y1]);
        }else{
            vis[x][y]=true;
            dfs(x1,y1);
            f[x][y]=f[x1][y1]+a[x][y]-a[x1][y1];
        }
    }
    if(vis[x][y])return;
    else{
        f[x][y]=0;
        vis[x][y]=true;
        return;
    }
}
int main(){
    int i,j,res=0;
    cin>>n>>m;
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            cin>>a[i][j];
        }
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j){
            if(!vis[i][j])dfs(i,j);
        } 
    } 
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j)res=max(res,f[i][j]);
    }
    cout<<res+1;
    return 0;
}

by Q294 @ 2022-01-25 15:19:01

#include<cstdio>
#include<algorithm>
#define r(i,a,b) for (int i=a;i<=b;i++)
#define pk putchar(32)
#define ph putchar(10)
using namespace std;int t,n,m;
struct wyc{
    int x,y,h;
}f[10001];//h高度，x横坐标，y纵坐标
int l[10001];//每个点的最优解
int ans;//最优解
int max(int x,int y){return x>y?x:y;}int min(int x,int y){return x<y?x:y;}
short dx[4]={-1,0,1,0};//四个方向扩展
short dy[4]={0,1,0,-1};
void read(int &a)//输入优化
{
    a=0;int d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;a=a*10+c-48;
    while (c=getchar(),c>='0'&&c<='9') a=a*10+c-48;
    a*=d;
}
void write(int x)//输出优化
{
    if (x<0) {x=-x;putchar(45);}
    if (x>9) write(x/10);
    putchar(x%10+48);return;
}
bool cmp(wyc x,wyc y){return x.h>y.h;}//按高度排序
void LRZ()
{
    int b;
    read(b);read(m);//这里用b，是为了方便保存横纵坐标
    r(i,1,b)
     r(j,1,m)
     {
      read(f[++n].h);
      f[n].x=i;//横坐标
      f[n].y=j;//纵坐标
     }
    sort(f+1,f+1+n,cmp);//排序
}
bool check(int i,int j)//看f[i]能否到达f[j]
{
    r(k,0,3)
     if (f[i].x+dx[k]==f[j].x&&f[i].y+dy[k]==f[j].y) return true;//可以到达
    return false;//否则
}
void dp()
{
    r(i,1,n){
        l[i]=1;//每个点的初始长度就是1
     for (int j=i-1;j>0;j--)
          if (check(i,j)&&f[j].h>f[i].h)//如果可以到达
           l[i]=max(l[i],l[j]+1);//动态转移
    }
    r(i,1,n)
     ans=max(ans,l[i]);
    write(ans);//输出
}
int main()
{
    LRZ();
    dp();
}

by witw @ 2022-01-25 17:16:33

@Q294 为啥每个点初始长度是1啊，不是根据距离长度不是由两点长度差决定的吗

by Q294 @ 2022-01-25 18:30:03

某个点滑向上下左右相邻四个点之一，当且仅当高度会减小（从 24开始，在 1结束）。 他最短的距离是2—1

by witw @ 2022-01-25 20:55:28

@Q294 晓得了，Thanks♪(･ω･)ﾉ