题解 P1434 【滑雪】

这一题，看上去像是DP，但经过分析+标签，确定使用 ###记忆化搜索 首先来分析一般搜索的情况，最坏情况（样例），每个点都要搜到，枚举每个点O（n²），搜O（nlogn）不止，合起来就是O（n³logn）还不止，虽然能过，但是这**显然**不是最好的 首先讲一下算法： 1.由于不晓得从何处开滑，所以要以每个点为源搜一遍 2.每次搜索，都枚举周围4个点，如果可以去，就搜索那个点，具体实现： ```cpp int tmp=0; if (a[x][y]>a[x-1][y]) tmp=max(tmp,dfs(x-1,y)+1); if (a[x][y]>a[x+1][y]) tmp=max(tmp,dfs(x+1,y)+1); if (a[x][y]>a[x][y-1]) tmp=max(tmp,dfs(x,y-1)+1); if (a[x][y]>a[x][y+1]) tmp=max(tmp,dfs(x,y+1)+1); return tmp; ------>严肃，此时我们会发现，当调用dfs(2,1)和dfs(1,2)时，都会搜索dfs(1,1)，完全是浪费，因为此时1,1的解可能已经求出 ``` 而我们用f[1][1]保存好1,1的解，就可以避免冗余，这也就是记忆化搜索 f数组初始化为0，如果已经搜过，f数组保存该点最优解，当调用dfs(x,y)时，先检查f[x][y]，若不为0，则可以直接返回f值，否则再进行计算，计算完毕后，将结果保存至f数组，就可以在下一次运算中直接调用 记忆化搜索代码如下 ```cpp #define maxn 100+5 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int r,c; int f[maxn][maxn],a[maxn][maxn]; int dfs(int x,int y) { if (x>0 && x<=r && y>0 && y<=c) return 1; if (f[x][y]) return f[x][y]; int tmp=0; if (a[x][y]>a[x-1][y]) tmp=max(tmp,dfs(x-1,y)+1); if (a[x][y]>a[x+1][y]) tmp=max(tmp,dfs(x+1,y)+1); if (a[x][y]>a[x][y-1]) tmp=max(tmp,dfs(x,y-1)+1); if (a[x][y]>a[x][y+1]) tmp=max(tmp,dfs(x,y+1)+1); f[x][y]=tmp; return f[x][y]; } int main() { 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) f[i][j]=0; int ans=0; for (int i=1;i<=r;++i) for (int j=1;j<=c;++j) { f[i][j]=dfs(i,j); ans=max(ans,f[i][j]); } // for (int i=1;i<=r;++i,cout << endl) // for (int j=1;j<=c;++j) // cout << f[i][j] << " "; cout << ans; return 0; } ``` DP也非不可（juruo只是想过） 用dp[i,j]表示滑到i，j的最长路，可以为此dp4遍，一遍向右，一遍向左，一遍向上，一遍向下，然后取最大值即可 今年pj第三题，本人小学，写了半天DFS，还TLE，后来才发现那题可以DP，类似这题 喵，就是这样