/ Vijos / 题库 / 清帝之惑之顺治 /

题解

358 条题解

  • 7
    @ 2017-09-11 22:49:19

    直接记忆化......

    #include <stdio.h>
#include <algorithm>
using namespace std;

int n,m;
int a[505][505];
int dp[505][505];
int vis[505][505];
int ans;

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

int dfs(int x,int y)
{
    if(vis[x][y]) return dp[x][y];
    vis[x][y]=1;
    int flag=0;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1 || nx>n || ny<1 || ny>m || a[nx][ny]>=a[x][y]) continue;
        flag=1;
        dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
    }
    if(flag==0) dp[x][y]=1;
    ans=max(ans,dp[x][y]);
    return dp[x][y];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dfs(i,j);
    printf("%d",ans);
    return 0;
}
  • 2
    @ 2019-12-11 17:14:01

    题目分析

    用\(dp[i][j]\)代表从第\(i\)行第\(j\)列出发的最长滑道长度，\(dp\)方程显然是四周高度比\((i,j)\)小的坐标的\(dp\)值的最大值\(+1\)，问题是，以怎么样的先后顺序来维护这一系列\(dp\)方程呢？我们可以想到，不论先后顺序是怎么样的，只要保证\(dp[i][j]\)只被计算一次，那么最后总的时间复杂度就会是\(O(n^2)\)。也就是说可以用记忆化搜索的方法。

    这里提一个记忆化搜索的小技巧：一开始初始化\(dp[i][j]=-1\)，这显然是一个非法值，于是我们可以用\(~dp[i][j]\)判断\(dp[i][j]\)是否已经被计算过，不必开一个bool数组来保存。

    Code

    #include <bits/stdc++.h>
using namespace std;
int dp[501][501];
int h[501][501];
int mx[]={0,1,0,-1};
int my[]={1,0,-1,0};
int n,m;
int solve(int x,int y){
    if (~dp[x][y]) return dp[x][y];
    int ans=1;
    for (int i=0;i<4;++i){
        int dx=x+mx[i];
        int dy=y+my[i];
        if (dx>=0 && dx<n && dy>=0 && dy<m && h[dx][dy]<h[x][y]) ans=max(ans,solve(dx,dy)+1);
    }
    dp[x][y]=ans;
    return ans;
}
int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;++i)
        for (int j=0;j<m;++j) scanf("%d",&h[i][j]);
    int ans=0;
    for (int i=0;i<n;++i)
        for (int j=0;j<m;++j) ans=max(ans,solve(i,j));
    printf("%d",ans);
}
  • 2
    @ 2019-03-16 19:44:06

    #include <cstdio>
    #include <cstring>
    using namespace std;
    int n,m,ans,res;
    int a[1005][1005],b[1005][1005];
    int lx[4]={0,1,0,-1};
    int ly[4]={1,0,-1,0};

    bool ok(int x,int y)
    {
    if(x<1 || x>n)return false;
    if(y<1 || y>m)return false;
    return true;
    }

    int dp(int x,int y)
    {
    if(b[x][y]>0)return b[x][y];
    int xx,yy,res=0,ans=0;
    for(int i=0;i<4;i++)
    {
    xx=x+lx[i];yy=y+ly[i];
    if((a[xx][yy]>a[x][y])&&ok(xx,yy))
    {
    res=dp(xx,yy)+1;
    if(res>ans)ans=res;
    }
    }
    b[x][y]=ans;
    return ans;
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    memset(b,-1,sizeof(b));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
    res=dp(i,j)+1;
    if(res>ans)ans=res;
    }
    printf("%d\n",ans);
    return 0;
    }

  • 2
    @ 2019-01-30 11:22:20 
    #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Dor(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define N 505
using namespace std;

//核心：记忆化搜索 
int f[N][N],n,m,map[N][N],ans;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dfs(int l,int r){   
    if (f[l][r]) return f[l][r];
    int flag=0;
    For(i,0,3){
        int gx=l+dx[i],gy=r+dy[i];
        if (gx>0 && gx<=n && gy>0 && gy<=m && map[gx][gy]<map[l][r]){
            f[l][r]=max(f[l][r],dfs(gx,gy)+1);
            flag=1;     
        }
    }
    if (!flag) f[l][r]=1;
    ans=max(ans,f[l][r]);
    return f[l][r];
}
int main(){
    scanf("%d%d",&n,&m);
    For(i,1,n) For(j,1,m) scanf("%d",&map[i][j]);
    For(i,1,n) For(j,1,m) dfs(i,j);
    printf("%d\n",ans);
    return 0;
}
  • 1
    @ 2021-10-23 21:10:14

    #include<bits/stdc++.h>//注意一下哈，比赛不适合用万能头
    using namespace std;

    int n,m;
    int a[505][505];
    int dp[505][505];
    int vis[505][505];
    int ans;

    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};

    int dfs(int x,int y)
    {
    if(vis[x][y]) return dp[x][y];
    vis[x][y]=1;
    int flag=0;
    for(int i=0;i<4;i++)
    {
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<1 || nx>n || ny<1 || ny>m || a[nx][ny]>=a[x][y]) continue;
    flag=1;
    dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
    }
    if(flag==0) dp[x][y]=1;
    ans=max(ans,dp[x][y]);
    return dp[x][y];
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dfs(i,j);
    printf("%d",ans);
    return 0;
    }

  • 1
    @ 2018-02-01 11:40:48

    没用DFS记忆化，优先队列实现

    优先队列插入高度值，高度高的先出队。然后用pair加坐标压缩绑定高度和坐标，使其能同时加入队列并排序。

    #include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define MAXR 505
#define NEGINF -2100000000
using namespace std;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
typedef pair<int, int> pii;
int matrix[MAXR][MAXR];
int dp[MAXR][MAXR] = {0};
priority_queue<pii> pq;

int main(){
  int maxlen = 0;
  int r, c;
  cin >> r >> c;
  for(int i=0; i<r; i++){
    for(int j=0; j<c; j++){
      cin >> matrix[i][j];
      pq.push(make_pair(matrix[i][j], i*c+j));
      dp[i][j] = NEGINF;
    }
  }
  pii p;
  int h, tr, tc, tx, ty;
  while(!pq.empty()){
    p = pq.top();
    pq.pop();
    h = p.first;
    tc = p.second % c;
    tr = p.second / c;
    dp[tr][tc] = 1;
    for(int i=0; i<4; i++){
      tx = tc + dx[i];
      ty = tr + dy[i];
      if(tx>=0 && tx < c && ty >=0 && ty < r && h < matrix[ty][tx]){
        dp[tr][tc] = max(dp[tr][tc], dp[ty][tx]+1);
      }
    }
    maxlen = max(maxlen, dp[tr][tc]);
  }
  cout << maxlen;

  return 0;
}

    时间空间使用量

     Accepted
#   状态  耗时  内存占用
#1  Accepted    133ms   4.359 MiB
#2  Accepted    18ms    2.566 MiB
#3  Accepted    31ms    2.074 MiB
#4  Accepted    6ms     844.0 KiB
#5  Accepted    70ms    3.566 MiB
#6  Accepted    7ms     836.0 KiB
#7  Accepted    6ms     1.352 MiB
#8  Accepted    45ms    2.219 MiB
#9  Accepted    17ms    1.75 MiB
#10     Accepted    85ms    3.969 MiB
  • 1
    @ 2017-09-11 22:49:41

    记忆化搜索即可

    #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=505;
int n,m;
int W[MAXN][MAXN];
int e[MAXN][MAXN];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int dfs(int i,int j)
{
//  if(W[i+1][j]>=W[i][j]&&W[i][j+1]>=W[i][j]&&W[i-1][j]>=W[i][j]&&W[i][j-1]>=W[i][j])
//      return 0;
    if(e[i][j]) return e[i][j];
    int &ans=e[i][j]=0;
    for(int k=0;k<4;++k)
    {
        int nx=i+dx[k];
        int ny=j+dy[k];
        if(W[nx][ny]<W[i][j]) ans=max(ans,dfs(nx,ny)+1);
    }
    return ans;
}


int main()
{
    memset(W,63,sizeof W);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&W[i][j]);
    int ans=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            ans=max(ans,dfs(i,j));
    printf("%d",ans+1);
    return 0;
}
    • @ 2018-05-09 20:24:37

      为什么ans前加“&”时间就很优，大概几十ms，不加“&”就会超时呢？求教。

  • 0
    @ 2021-05-06 17:09:19

    #include <stdio.h>
    #include <algorithm>
    using namespace std;

    int n,m;
    int a[505][505];
    int dp[505][505];
    int vis[505][505];
    int ans;

    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};

    int dfs(int x,int y)
    {
    if(vis[x][y]) return dp[x][y];
    vis[x][y]=1;
    int flag=0;
    for(int i=0;i<4;i++)
    {
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<1 || nx>n || ny<1 || ny>m || a[nx][ny]>=a[x][y]) continue;
    flag=1;
    dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
    }
    if(flag==0) dp[x][y]=1;
    ans=max(ans,dp[x][y]);
    return dp[x][y];
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dfs(i,j);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2020-12-20 16:26:42 
    #include<bits/stdc++.h>
using namespace std;
int fx[]={0,-1,0,1,0};
int fy[]={0,0,1,0,-1};
long long r, c, t, v;
int p[501][501];
int dp[501][501]; 
int dfs(int x, int y){//max_length of x~y
    int f, d, nx, ny;
    if(dp[x][y]>0){//记忆化,已求出,不必递归了 
        return dp[x][y]; 
    }
    f=1;
    for(int i=1;i<=4;i++){//能达到p[x][y]的点(p[nx][ny]<p[x][y])
        nx=x+fx[i];
        ny=y+fy[i];
        if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&p[x][y]<p[nx][ny]){//边界 
            d=dfs(nx,ny)+1;//递归 
            if(d>f) f=d;
        } 
    }
    dp[x][y]=f;
    return f;
} 
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>p[i][j];//input high
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            t=dfs(i,j);
            dp[i][j]=t;
            if(t>v) v=t;//max_length
        }
    }
    cout<<v;
    return 0;
}
  • 0
    @ 2020-12-20 16:26:33 
    #include<bits/stdc++.h>
using namespace std;
int fx[]={0,-1,0,1,0};
int fy[]={0,0,1,0,-1};
long long r, c, t, v;
int p[501][501];
int dp[501][501]; 
int dfs(int x, int y){//max_length of x~y
    int f, d, nx, ny;
    if(dp[x][y]>0){//记忆化,已求出,不必递归了 
        return dp[x][y]; 
    }
    f=1;
    for(int i=1;i<=4;i++){//能达到p[x][y]的点(p[nx][ny]<p[x][y])
        nx=x+fx[i];
        ny=y+fy[i];
        if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&p[x][y]<p[nx][ny]){//边界 
            d=dfs(nx,ny)+1;//递归 
            if(d>f) f=d;
        } 
    }
    dp[x][y]=f;
    return f;
} 
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>p[i][j];//input high
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            t=dfs(i,j);
            dp[i][j]=t;
            if(t>v) v=t;//max_length
        }
    }
    cout<<v;
    return 0;
}
  • 0
    @ 2019-04-16 20:02:01

    #include<stdio.h>
    int n,m,a[501][501],dp[501][501],ans,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    int k[501][501];
    int max(int x,int y){
    if(x>y)
    return x;
    return y;

    }
    int dfs(int x,int y){
    if(k[x][y])
    return dp[x][y];
    k[x][y]=1;
    int flag=0;
    for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]>=a[x][y])
    continue;
    flag=1;
    dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
    }
    if(flag==0)
    dp[x][y]=1;
    ans=max(ans,dp[x][y]);
    return dp[x][y];
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dfs(i,j);
    printf("%d",ans);
    }

  • 0
    @ 2019-04-16 20:01:47

    #include<stdio.h>
    int n,m,a[501][501],dp[501][501],ans,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    int k[501][501];
    int max(int x,int y){
    if(x>y)
    return x;
    return y;

    }
    int dfs(int x,int y){
    if(k[x][y])
    return dp[x][y];
    k[x][y]=1;
    int flag=0;
    for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]>=a[x][y])
    continue;
    flag=1;
    dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
    }
    if(flag==0)
    dp[x][y]=1;
    ans=max(ans,dp[x][y]);
    return dp[x][y];
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dfs(i,j);
    printf("%d",ans);
    }

  • 0
    @ 2018-12-02 15:59:33

    记忆化搜索或者排序（由于后者比较好写，这里我就介绍排序的方法）
    ..................................................
    首先，我们很容易可以看出这是把最长升从线做到了平面，所以我们可以排一趟序，同时标记原来的位置，再从最低到最高进行判断，求出答案

    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    int n,m,ans;
    int map[1000005],f[1000005],p[1000005],h[1000005];
    bool vis[1000005];

    void qsort(int l,int r)
    {
    int i=l,j=r,mid=map[rand()%(r-l+1)+l],t;
    do {
    while (map[i]<mid) i++;
    while (map[j]>mid) j--;
    if (i<=j) {
    t=map[i];map[i]=map[j];map[j]=t;
    t=p[i];p[i]=p[j];p[j]=t;
    i++;j--;
    }
    } while (i<=j);
    if (i<r) qsort(i,r);
    if (l<j) qsort(l,j);
    }
    int main()
    {
    int x,y;
    scanf("%d%d",&n,&m);
    ans=0;
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n*m;i++)
    {
    scanf("%d",&map[i]);
    h[i]=map[i];
    p[i]=i;
    }
    qsort(1,n*m);
    for (int i=1;i<=n*m;i++)
    {
    x=p[i]/m;y=p[i]%m;
    if (y!=1&&vis[p[i]-1]==true&&h[p[i]]>h[p[i]-1]) f[p[i]]=max(f[p[i]],f[p[i]-1]);
    if (y!=m&&vis[p[i]+1]==true&&h[p[i]]>h[p[i]+1]) f[p[i]]=max(f[p[i]],f[p[i]+1]);
    if (x!=1&&vis[p[i]-m]==true&&h[p[i]]>h[p[i]-m]) f[p[i]]=max(f[p[i]],f[p[i]-m]);
    if (x!=n&&vis[p[i]+m]==true&&h[p[i]]>h[p[i]+m]) f[p[i]]=max(f[p[i]],f[p[i]+m]);
    f[p[i]]++;vis[p[i]]=true;
    }
    for (int i=1;i<=n*m;i++) ans=max(ans,f[i]);
    printf("%d",ans);
    }

  • 0
    @ 2017-07-16 20:59:14 
    #include <iostream>
using namespace std;
int r, c;
int a[503][503], d[503][503];
int dfs(int x, int y, int k){
    if(x == 0 || y == 0 || x > r || y > c)
        return 0;
    
    if(d[x][y] != 0)
        return d[x][y];
        
    return d[x][y] = 1 + 
                     max( 
                        max( a[x-1][y] < a[x][y] ? dfs(x-1, y, k+1) : 0, 
                             a[x+1][y] < a[x][y] ? dfs(x+1, y, k+1) : 0),
                        max( a[x][y-1] < a[x][y] ? dfs(x, y-1, k+1) : 0, 
                             a[x][y+1] < a[x][y] ? dfs(x, y+1, k+1) : 0) );
}
int main(){
    int ans = 0;
    cin >> r >> c;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            cin >> a[i][j];
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            ans = max(ans, d[i][j] = dfs(i, j, 1));
    cout << ans << endl;    
    return 0;
}
  • 0
    @ 2017-06-07 13:21:36

    发现没有明显的拓扑顺序，所以使用记忆化搜索。

    AC c++:

    #include <iostream>
using namespace std;

const int maxsize = 510;
int r, c, h[maxsize][maxsize], dp[maxsize][maxsize];

int get(int i, int j) {
    if (dp[i][j] != 1) return dp[i][j];
    int _max = 1;
    if (i - 1 >= 0 && h[i][j] > h[i - 1][j]) {
        _max = max(get(i - 1, j) + 1, _max);
    }
    if (j - 1 >= 0 && h[i][j] > h[i][j - 1]) {
        _max = max(get(i, j - 1) + 1, _max);    
    }
    if (i + 1 < r && h[i][j] > h[i + 1][j]) {
        _max = max(get(i + 1, j) + 1, _max);    
    }
    if (j + 1 < c && h[i][j] > h[i][j + 1]) {
        _max = max(get(i, j + 1) + 1, _max);    
    }
    return dp[i][j] = _max;
}

int main() {
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            cin >> h[i][j];
            dp[i][j] = 1;
        }
    int result = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            result = max(result, get(i, j));
        }       
    }
    cout << result << endl;
    return 0;
}

    附: (评测结果)
    #1 Accepted 89ms 2.305MiB
    #2 Accepted 18ms 2.195MiB
    #3 Accepted 27ms 1.059MiB
    #4 Accepted 6ms 700.0KiB
    #5 Accepted 57ms 1.68MiB
    #6 Accepted 11ms 712.0KiB
    #7 Accepted 7ms 1.184MiB
    #8 Accepted 40ms 1.309MiB
    #9 Accepted 21ms 1.262MiB
    #10 Accepted 79ms 2.191MiB

  • 0
    @ 2017-05-28 13:54:26

    Accepted

    状态 耗时 内存占用

    #1 Accepted 97ms 2.25MiB
    #2 Accepted 20ms 2.0MiB
    #3 Accepted 28ms 1.0MiB
    #4 Accepted 12ms 640.0KiB
    #5 Accepted 57ms 1.625MiB
    #6 Accepted 11ms 768.0KiB
    #7 Accepted 13ms 1.0MiB
    #8 Accepted 40ms 1.168MiB
    #9 Accepted 19ms 1.109MiB
    #10 Accepted 76ms 2.25MiB
    代码

    #include<iostream>
using namespace std;
int h[505][505],r,c,ans=0,f[505][505];
short dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dp(int a,int b)
{
    f[a][b]=0;
    for(int t=0;t<4;t++)
    {
        if(h[a][b]>h[a+dx[t]][b+dy[t]])
        {
            if(f[a+dx[t]][b+dy[t]]==0)
                dp(a+dx[t],b+dy[t]);
            if(f[a][b]<f[a+dx[t]][b+dy[t]])
                f[a][b]=f[a+dx[t]][b+dy[t]];
        }
    }
    f[a][b]++;
}
int main()
{
    cin>>r>>c;
    for(int i=0;i<=r+1;i++)
        for(int j=0;j<=c+1;j++)
            h[i][j]=10001;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>h[i][j];
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            dp(i,j);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            if(ans<f[i][j])
                ans=f[i][j];
    cout<<ans;
    return 0;
}
  • 0
    @ 2017-05-07 12:46:09

    /*
    一道动态规划题(记忆化搜索做)
    我们发现可以完整表示一个状态的需求只要有(x,y)就可以了
    即起点(x,y)固定
    那么从这个点出发能滑到的最长长度就是确定了的~
    很容易发现这里是有很多重叠子问题的~
    同时具有最优子结构和无后效性
    所以我们可以用用f[x][y]表示在(x,y)所能到达的最长长度
    那么我们用个记忆化搜索搜一下
    高度数组可以预设无穷大表示不能走~
    这样就可以不用判断边界了因为一定不会走到了
    当然也可以扩展的时候特判一下边界
    最后找到f[][]的最大值即可
    */

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=505;
int h[MAXN][MAXN];
int f[MAXN][MAXN];
int n,m;
int ans;
int zx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void init()
{
    memset(h,0x3f,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&h[i][j]);
}

int dfs(int x,int y)
{
    if(f[x][y])
        return f[x][y];
    int res=1;
    for(int i=0;i<4;i++)
    {
        int newx=x+zx[i][0];    int newy=y+zx[i][1];
        if(h[x][y]>h[newx][newy])
            res=max(res,dfs(newx,newy)+1);
    }
    return f[x][y]=res;
}

void DP()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!f[i][j])
                dfs(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,f[i][j]);
    cout<<ans<<endl;
}

int main()
{
    init();
    DP();
}
    • @ 2018-10-18 15:20:43

      你好，能具体写一下你的dfs函数的意思吗？没有看懂！谢谢了

  • 0
    @ 2016-08-17 16:30:13 
    #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxx = 510;
int ans;
int r, c;
int h[maxx][maxx];
int f[maxx][maxx];

int dp (int x, int y) {
    if (f[x][y]) return f[x][y];
    int res = 0;
    if (h[x][y - 1] < h[x][y]) res = max (res, dp (x, y - 1));
    if (h[x][y + 1] < h[x][y]) res = max (res, dp (x, y + 1));
    if (h[x - 1][y] < h[x][y]) res = max (res, dp (x - 1, y));
    if (h[x + 1][y] < h[x][y]) res = max (res, dp (x + 1, y));
    return f[x][y] = res + 1;
}

int main ()
{
    //freopen ("in.txt", "r", stdin);
    memset (h, 0x3f, sizeof (h));
    cin >> r >> c;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> h[i][j];
        }
    }
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            if (!f[i][j]) dp (i, j);
            ans = max (ans, f[i][j]);
        }
    }
    cout << ans;
    return 0;
}
    • @ 2016-09-28 19:47:59

      int dp (int x, int y) {
      if (f[x][y]) return f[x][y];
      int res = 0;
      if (h[x][y - 1] < h[x][y]) res = max (res, dp (x, y - 1));
      if (h[x][y + 1] < h[x][y]) res = max (res, dp (x, y + 1));
      if (h[x - 1][y] < h[x][y]) res = max (res, dp (x - 1, y));
      if (h[x + 1][y] < h[x][y]) res = max (res, dp (x + 1, y));
      return f[x][y] = res + 1;
      }
      你好，这个函数中存在数组越界问题。

  • 0
    @ 2016-03-03 14:19:35 
        #include<iostream>
    #include<cstring>
    using namespace std;
    int g[600][600],l[600][600];
    int r,c;
    int ans=0;
    void dfs(int x,int y,int d)
    {
        if(d<=l[x][y])return;
        l[x][y]=d;
        if(d>ans)ans=d;
        if(g[x][y]>g[x-1][y])dfs(x-1,y,d+1);
        if(g[x][y]>g[x][y-1])dfs(x,y-1,d+1);
        if(g[x][y]>g[x+1][y])dfs(x+1,y,d+1);
        if(g[x][y]>g[x][y+1])dfs(x,y+1,d+1);
    }
    int main()
    {
        cin>>r>>c;
        memset(g,127/2,sizeof(g));
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                cin>>g[i][j];
        memset(l,0,sizeof(l));
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                dfs(i,j,1);
        cout<<ans;
        return 0;
    }
  • 0
    @ 2015-07-12 00:38:35

    ​

    P1011清帝之惑之顺治
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1011 清帝之惑之顺治
    递交时间 2015-07-12 00:38:11
    代码语言 C++
    评测机 VijosEx
    消耗时间 261 ms
    消耗内存 2252 KiB
    评测时间 2015-07-12 00:38:13

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 62 ms, mem = 2252 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 2252 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 2248 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 2252 KiB, score = 10

    测试数据 #4: Accepted, time = 46 ms, mem = 2248 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 2248 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 2248 KiB, score = 10

    测试数据 #7: Accepted, time = 31 ms, mem = 2248 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 2252 KiB, score = 10

    测试数据 #9: Accepted, time = 62 ms, mem = 2248 KiB, score = 10

    Accepted, time = 261 ms, mem = 2252 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    int r , c;
    int a[500 + 2][500 + 2];
    int f[500 + 2][500 + 2];
    int i , j;
    int ans;

    int dp( int x , int y )
    {
    if( f[x][y] != -1 )
    return f[x][y];
    if( a[x - 1][y] < a[x][y] && x - 1 > 0 )
    f[x][y] = max( f[x][y] , dp( x - 1 , y ) );
    if( a[x + 1][y] < a[x][y] && x + 1 <= r )
    f[x][y] = max( f[x][y] , dp( x + 1 , y ) );
    if( a[x][y - 1] < a[x][y] && y - 1 > 0 )
    f[x][y] = max( f[x][y] , dp( x , y - 1 ) );
    if( a[x][y + 1] < a[x][y] && y + 1 <= c )
    f[x][y] = max( f[x][y] , dp( x , y + 1 ) );
    f[x][y]++;
    return f[x][y];
    }

    int main()
    {
    scanf( "%d %d" , &r , &c );
    for( i = 1 ; i <= r ; i++ )
    for( j = 1 ; j <= c ; j++ )
    scanf( "%d" , &a[i][j] );
    memset( f , -1 , sizeof( f ) );
    for( i = 1 ; i <= r ; i++ )
    for( j = 1 ; j <= c ; j++ )
    ans = max( ans , dp( i , j ) );
    cout << ans + 1 << endl;
    return 0;
    }

清帝之惑之顺治

信息

ID
1011
难度
6
分类
动态规划 点击显示
标签
递交数
10384
已通过
2952
通过率
28%
被复制
29
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1