B - 滑雪 POJ - 1088——dfs+记忆化搜索-蒲公英云

B - 滑雪 POJ - 1088——dfs+记忆化搜索

Think:
1知识点：dfs+记忆化搜索
1>记忆化搜索=搜索的形式+动态规划的思想
2>记忆化搜索简介：
记忆化搜索：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。
更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，
以后再次遇到这个状态的时候，就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点
——参考自百度百科
2题目分析：时间复杂度要求较高，单独dfs超时，需要记忆化记录中间已经得到的状态

以下为Accepted代码——16ms

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int R, C, e[114][114], book[114][114];
int jk[4][2]={
   {
   0,1},{
   1,0},{
   0,-1},{-1,0}};
int dfs(int x, int y);
bool Judge(int dx, int dy);
int main(){
    int i, j, mav;
    while(~scanf("%d %d", &R, &C)){
        memset(book, 0, sizeof(book));
        for(i = 1; i <= R; i++){
            for(j = 1; j <= C; j++){
                scanf("%d", &e[i][j]);
            }
        }
        mav = 1;
        for(i = 1; i <= R; i++){
            for(j = 1; j <= C; j++){
                mav = max(mav, dfs(i, j));
            }
        }
        printf("%d\n", mav);
    }
    return 0;
}
bool Judge(int dx, int dy){
    if(dx < 1 || dx > R || dy < 1 || dy > C)
        return false;
    else
        return true;
}
int dfs(int x, int y){
    if(book[x][y])
        return book[x][y];
    int k = 1;
    for(int i = 0; i < 4; i++){
        int dx = x + jk[i][0];
        int dy = y + jk[i][1];
        if(Judge(dx, dy) && e[dx][dy] < e[x][y])
            k = max(dfs(dx, dy)+1, k);
    }
    return book[x][y] = k;
}

以下为Accetped代码——110ms

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node{
    int x;
    int y;
    int w;
}a[11400];
int R, C, cnt, e[114][114], book[114][114], vis[114][114];
int jk[4][2]={
   {
   0,1},{
   1,0},{
   0,-1},{-1,0}};
bool cmp(struct node aa, struct node bb){
    return aa.w < bb.w;
}
void dfs(int u, int v, int step);
bool Judge(int dx, int dy);
int main(){
    int i, j, u, v, ans;
    while(~scanf("%d %d", &R, &C)){
        int t1 = 0;
        for(i = 1; i <= R; i++){
            for(j = 1; j <= C; j++){
                scanf("%d", &e[i][j]);
                a[t1].x = i, a[t1].y = j, a[t1].w = e[i][j], t1++;
            }
        }
        sort(a, a+t1, cmp);
        ans = 1;
        memset(book, 0, sizeof(book));
        for(i = 0; i < t1; i++){
            u = a[i].x, v = a[i].y;
            cnt = 1;
            memset(vis, 0, sizeof(vis));
            vis[u][v] = 1;
            dfs(u, v, 1);
            book[u][v] = cnt;
            ans = max(ans, cnt);
        }
        printf("%d\n", ans);
    }
    return 0;
}
bool Judge(int dx, int dy){
    if(dx < 1 || dx > R || dy < 1 || dy > C)
        return false;
    else
        return true;
}
void dfs(int u, int v, int step){
    cnt = max(cnt, step);
    for(int i = 0; i < 4; i++){
        int dx = u + jk[i][0];
        int dy = v + jk[i][1];
        if(Judge(dx, dy)){
            if(book[dx][dy] && e[dx][dy] < e[u][v])
                cnt = max(cnt, step+book[dx][dy]);
            else if(e[dx][dy] < e[u][v]){
                vis[dx][dy] = 1;
                dfs(dx, dy, step+1);
                vis[dx][dy] = 0;
            }
        }
    }
}