跳至正文

tyvj 1004 滑雪

  • OI路程

  上午写了一次(http://zqynux.blog.163.com/blog/static/1674995972010101325737526/),只有70分,剩下的我也知道为什么错了,所以我的思路是不行的,但是我就想不到另外的方法了,到群里问了下,别人把代码发给我看了,, 汗, 好简单, 纯DP, 没有任何杂念, 我原本以为要排序, 但NOIP的题目似乎涉及不到这么高深的算法, 矩阵+排序+搜索, 就觉得我是想复杂了, 他这个代码太简单了…
  但是几乎是纯递归,我以为会爆掉(栈溢出), 结果用最最最大的可能用尽栈的数据测试, 结果没溢出, 后来测试发现,, 栈一般还是够用.. 
  但是我犯了一个很严重的错误, 记忆DP竟然没有给它记忆,, 所以导致最后一个数据超时了,,代码如下:

#include <stdio.h>
int map[100][100];
int dis[100][100];
int r, c;

int check(int a,
int b)
{
        if(a < 0 || a >= r
|| b < 0 || b >= c){
                return 0;
        }
        return 1;
}

int max(int a,
int b)
{
        return a > b ? a : b;
}

#define deal(i, j) do{\
        if(check(i, j) && map[i][j] >
map[a][b]){\

                t = max(srch(i, j),
t);\

        }\
}while(0)

int srch(int a, int b)
{
        int t = 0;
        if(dis[a][b] != 0){
                return dis[a][b];
        }
        deal(a +
1, b);
        deal(a – 1, b);
        deal(a, b + 1);
        deal(a, b – 1);
        /
        Mistack 1:
          真是….不好怎么评价自己了,, 记忆DP, 我竟然忘记记忆了..
        
/
        dis[a][b]
= t + 1;
        return dis[a][b];
}

int main(void)
{
        int ans = 1;
        int i, j,
t;
        scanf("%d%d", &r,
&c);
        for(i = 0; i < r; i++){
                for(j = 0; j < c;
j++){
                        scanf("%d",
&map[i][j]);
                }
        }
        for(i = 0; i < r;
i++){
                for(j = 0; j < c; j++){
                        t = srch(i,
j);
                        if(ans <
t){
                                ans =
t;
                        }
                }
        }
        printf("%d\n", ans);
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。