353 条题解

  • 6
    @ 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-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;
    }

  • 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
    @ 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
    @ 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;
    }
    
  • 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;
    }

  • 0
    @ 2015-05-28 20:22:07

    应该就是个搜索吧!

  • 0
    @ 2015-05-09 15:36:07

    #include<cstdio>
    #include<cstring>
    const int dx[4]={-1,0,1,0};//定义四种滑雪规则
    const int dy[4]={0,-1,0,1};
    int m[502][502];
    int f[502][502];
    int r,c;
    int search(int x,int y)
    {
    if (f[x][y]){//说明f[i][j]的最大距离已经确定
    return f[x][y];
    }
    int t=1;
    for (int i=0;i<4;i++)
    {
    int nx=x+dx[i];//nx,ny为移动后的坐标
    int ny=y+dy[i];
    if(nx<=r&&nx>=1&&ny<=c&&ny>=1&&m[x][y]<m[nx][ny])
    {//判断边界+比较高度
    int tmp=search(nx,ny)+1;
    if (tmp>t) t=tmp;//向上下左右搜找到一个最大值
    }
    }
    f[x][y]=t;//赋值,把搜索的值存下来,以便下次调用
    return t;
    }
    int main()
    {
    memset(m,0xff,sizeof(m));
    scanf("%d%d",&r,&c);
    for (int i=1;i<=r;i++)
    for (int j=1;j<=c;j++)
    scanf("%d",&m[i][j]);
    int ans=0;
    for (int i=1;i<=r;i++)
    for (int j=1;j<=c;j++)
    {
    f[i][j]=search(i,j);
    ans=f[i][j]>ans?f[i][j]:ans;
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2015-02-05 16:41:11

    备忘录方法处理起来比较容易,动态规划描述起来比较复杂。
    #include<iostream>
    #include<string.h>
    #include<math.h>
    #include<stdio.h>
    using namespace std;

    int a[505][505];
    int ans[505][505];
    int xsize, ysize;
    int f(int x, int y){
    if (x < 0 || y < 0)return 0;
    if (x >= xsize || y>=ysize)return 0;
    if (ans[x][y] == -1){
    ans[x][y] = 0;
    if (a[x][y]>a[x - 1][y])ans[x][y] = f(x-1,y);
    if (a[x][y]>a[x + 1][y] && ans[x][y] < f(x + 1, y))
    ans[x][y] = f(x + 1, y) ;
    if (a[x][y]>a[x][y - 1] && ans[x][y] < f(x, y - 1))
    ans[x][y] = f(x, y - 1) ;
    if (a[x][y]>a[x][y + 1] && ans[x][y] < f(x, y + 1) )
    ans[x][y] = f(x, y + 1) ;
    ans[x][y]++;
    }
    return ans[x][y];
    }
    int main(){
    freopen("in.txt", "r", stdin);
    cin >> xsize >> ysize;
    memset(ans, -1, sizeof(ans));
    int i, j;
    for (i = 0; i < xsize; i++){
    for (j = 0; j < ysize; j++){
    cin >> a[i][j];
    }
    }
    int ma=0;
    for (i = 0; i < xsize; i++){
    for (j = 0; j < ysize; j++){
    if (ma < f(i, j))ma = f(i, j);
    }
    }
    cout << ma << endl;
    return 0;
    }

  • 0
    @ 2015-02-05 10:21:52
  • 0
    @ 2015-01-08 21:38:54

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 89 ms, mem = 2700 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 2700 KiB, score = 10
    测试数据 #2: Accepted, time = 39 ms, mem = 2696 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 2700 KiB, score = 10
    测试数据 #4: Accepted, time = 62 ms, mem = 2700 KiB, score = 10
    测试数据 #5: Accepted, time = 7 ms, mem = 2700 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 2700 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 2700 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 2700 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 2696 KiB, score = 10
    Accepted, time = 334 ms, mem = 2700 KiB, score = 100

    ####**代码**
    program skiing;
    var
    a,f:array[0..500,0..500] of longint;
    i,j,r,c,ans:longint;
    function dp(x,y:longint):longint;
    var
    w:longint;
    begin
    if f[x,y]<>0 then exit(f[x,y]);
    if (x>1) and (a[x,y]>a[x-1,y]) then
    begin
    w:=dp(x-1,y);
    if w>f[x,y] then f[x,y]:=w;
    end;
    if (y>1) and (a[x,y]>a[x,y-1]) then
    begin
    w:=dp(x,y-1);
    if w>f[x,y] then f[x,y]:=w;
    end;
    if (x<r) and (a[x,y]>a[x+1,y]) then
    begin
    w:=dp(x+1,y);
    if w>f[x,y] then f[x,y]:=w;
    end;
    if (y<c) and (a[x,y]>a[x,y+1]) then
    begin
    w:=dp(x,y+1);
    if w>f[x,y] then f[x,y]:=w;
    end;
    f[x,y]:=f[x,y]+1;dp:=f[x,y];
    end;
    begin
    readln(r,c);
    for i:=1 to r do for j:=1 to c do read(a[i,j]);
    fillchar(f,sizeof(f),0);
    ans:=0;
    for i:=1 to r do
    for j:=1 to c do
    if ans<dp(i,j) then ans:=dp(i,j);
    writeln(ans);
    end.

    在多年的迷茫后,我终于发现了方向。
    原来后效性是可以用递归消除的……
    辅之以记忆化搜索后速度也很快……

    规定f[i,j]为(i,j)点开始的最长路线,则 f[i,j]=max{f[i-1,j],f[i,j-1],f[i+1,j],f[i,j+1]}+1

信息

ID
1011
难度
6
分类
动态规划 点击显示
标签
递交数
9482
已通过
2740
通过率
29%
被复制
1
上传者