首页 > 代码库 > hdu--1978--记忆化深度搜索||递推
hdu--1978--记忆化深度搜索||递推
这题 我开始的做法是 记忆化搜索 但是tm地竟然tle了。。。很想不通 因为数据很小啊 就100 虽然方案的总数可能会很大..
然后 我就去百度 记忆化搜索 看下是不是我用错方法了 事实证明 我虽然没有用错 但还是 学到了很多=-=、
其实 我很早以前 也看过关于 记忆化搜索的一些介绍 但是 并没有太多感觉 并不是那些作者写的不好 而是我的水平没到 感受不了。。
很多东西会在不知不觉中提升~
我想 将我读的这篇介绍 传到这篇博客里来 似乎只能上传照片和视频=-= 那我给个链接吧 传送
虽然里面的代码不是用C/C++写的 但其实不会太影响我们的阅读 重点是对于 动态规划 与 搜索思想的理解
------------touch me
然后 我继续回过头来检查自己的TLE代码 我去discuss里看了下别人的讨论 发现很多人用的都是 递推式的动态规划做的 看到了一个和我用相同的记忆化深搜做的
and then i got it
我对于maze[i][j]的处理太懒了...耗了太多时间..
我将tle与改后AC代码都放上来吧
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int n , m; 6 const int mod = 10000; 7 const int size = 110; 8 int maze[size][size]; 9 int dp[size][size];10 bool vis[size][size];11 12 int dfs( int x , int y )13 {14 if( x==n && y==m )15 return 1;16 if( vis[x][y] )17 return dp[x][y];18 if( maze[x][y]==0 )19 return 0;20 for( int i = x ; i<=n ; i++ )21 {22 for( int j = y ; j<=m ; j++ )23 {24 if( (i-x + j-y) > maze[x][y] || x==i && y==j )25 continue;26 else27 {28 dp[x][y] += dfs(i,j);29 if( dp[x][y]>=mod )30 dp[x][y] %= mod;31 }32 }33 }34 vis[x][y] = true;35 return dp[x][y];36 }37 38 int main()39 {40 cin.sync_with_stdio(false);41 int t , ans;42 while( cin >> t )43 {44 while( t-- )45 {46 memset( vis , false , sizeof(vis) );47 memset( dp , 0 , sizeof(dp) );48 cin >> n >> m;49 for( int i = 1 ; i<=n ; i++ )50 {51 for( int j = 1 ; j<=m ; j++ )52 {53 cin >> maze[i][j];54 }55 }56 ans = dfs(1,1);57 cout << ans << endl;58 }59 }60 return 0;61 }
*** 其实 vis数组 是可以不写的 因为完全可以通过if( dp[ x ] [ y ]）return dp[x][y]来做到 但是我习惯上 有时候会写上它 有助于理解
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int n , m; 6 const int mod = 10000; 7 const int size = 110; 8 int maze[size][size]; 9 int dp[size][size];10 bool vis[size][size];11 12 int dfs( int x , int y )13 {14 if( x==n && y==m )15 return 1;16 if( vis[x][y] )17 {18 return dp[x][y];19 }20 if( maze[x][y]==0 )21 return 0;22 for( int i = 0 ; i<=maze[x][y] ; i++ )23 {24 for( int j = 0 ; j+i<=maze[x][y] ; j++ )25 {26 if( !(i+j) || x+i>n || y+j>m )27 continue;28 else29 {30 dp[x][y] += dfs( x+i,y+j);31 if( dp[x][y]>=mod )32 dp[x][y] %= mod;33 }34 }35 }36 vis[x][y] = true;37 return dp[x][y];38 }39 40 int main()41 {42 cin.sync_with_stdio(false);43 int t , ans;44 while( cin >> t )45 {46 while( t-- )47 {48 memset( vis , false , sizeof(vis) );49 memset( dp , 0 , sizeof(dp) );50 cin >> n >> m;51 for( int i = 1 ; i<=n ; i++ )52 {53 for( int j = 1 ; j<=m ; j++ )54 {55 cin >> maze[i][j];56 }57 }58 ans = dfs(1,1);59 cout << ans << endl;60 }61 }62 return 0;63 }
稍微 解释下 有助于 初学者的我们来理解：
因为是 深搜 所以这是递归的 我们可以将dp[ x ] [ y ]看成在N * M的地图里有多少种方式从（N,M)这个终点走到(X,Y)这个点 然后你可能会遇到dp[ x1 ] [ y1 ]与dp[ X2 ][ y2]都需要求得dp[ x3 ][ y3 ]那么我们只要将这个值给保存下来 在(x1,y1),(x2,y2)需要的时候 直接给它们就可以了 这里就有着DP对于重叠子问题的处理 而递归又是深搜的体现
这里 有一个边界注意下 就是(N,M) 当你搜索到这个点时 就可以看成是 递归出口了 然后直接返回一个 1 就可以了
我们再来讲下 递推的处理
这就和递归 完全2个方向 可以这样想 一个是 自底向上 一个是顶向下 dp[ x ][ y ]就变成了是N*M的地图里有多少种方式从(1,1)走到(x,y)这个点
其余多的解释 我也讲不来了 并且 我不确认 我以上所讲 都是正确的 都是我自己的理解 欢迎 探讨=-=
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 110; 6 const int mod = 10000; 7 int maze[size][size]; 8 int dp[size][size]; 9 10 int main()11 {12 cin.sync_with_stdio(false);13 int n , m , t;14 while( cin >> t )15 {16 while( t-- )17 {18 cin >> n >> m;19 for( int i = 1 ; i<=n ; i++ )20 {21 for( int j = 1 ; j<=m ; j++ )22 {23 cin >> maze[i][j];24 }25 }26 memset( dp , 0 , sizeof(dp) );27 dp[1][1] = 1;28 for( int i = 1 ; i<=n ; i++ )29 {30 for( int j = 1 ; j<=m ; j++ )31 {32 for( int p = 0 ; p<=maze[i][j] ; p++ )33 {34 for( int q = 0 ; p+q<=maze[i][j] ; q++ )35 {36 if( !(p+q) || p+i>n || q+j >m )37 continue;38 else39 {40 dp[i+p][j+q] += dp[i][j];41 if( dp[i+p][j+q]>=mod )42 dp[i+p][j+q] %= mod;43 }44 }45 }46 }47 }48 cout << dp[n][m] <<endl;49 }50 }51 return 0;52 }
其实我觉得 刚接触dfs的时候 并不是那么容易理解 或者 像我这种迟钝点的 我写了下面一段小小的代码 有助于理解=-=
#include <iostream>using namespace std;void dfs( char ch,int x ){ char zh = ch + 1; x+=2; for( int i = x ; i<=10 ; i+=2 ) { cout << ch << " " << i << endl; dfs(zh,i); }}int main(){ dfs(‘a‘,1);}
today:
在虎扑看到了个很有感触的帖子...选了里面一些jr的回帖 当做today:
和前女友异地恋，她经常主动打电话给我，有一天我嫌烦了，就对她说以后没事少给我打电话。她委屈地对我说：“想到你一个人在外地工作，身边一个朋友都没有，一个人吃饭，住房，我就很心疼，所以才老打电话给你。“
分手的那天：“我觉得我十年后肯定不是这样，但是你十年后还是现在这个样子。”
每天一点点努力，就是不想让下一个女人再说这种话。
她：“在网吧？有件事想和你说。”
我：“现在没空，晚上回你。“
大二在宿舍：
她：“在睡觉呢？今天没点名，不过明天早上上课把你的看电影带过来给我看看好吗？”
我：“哦，明天有课？”
第二天继续睡觉。。。
大三夜里失眠：
我短信：“我还有机会吗？”
她回复：“黄花菜都凉了！”
毕业一年：
她：“我下月结婚，你能来吗？”
我：“这几个月在外派啊，估计赶不回来。”
毕业两年：
她：“帮我给宝宝取个名字吧，男孩。”
我：“哈，读书少，不会取啊。大宝？”
她：“你个弱智，永远不上心。”
啪，挂掉。
大哥们，我承认我当初比较混蛋，更多的是她是女神，我是穷小子，想得多，自卑。当黄花菜凉的时候人家就已经有男朋友了，你们想让我怎么办，去挖墙脚吗？我一直知道自己辜负了她，所以更不想去打扰她的生活，至于之后的交流也更多的是朋友之间的互动。
另外，当初有点文艺，快临产的时候她知道是个男孩，名字一直定不下来，所以问了下我，真没有其他的意思。
也奉劝JRS，凡事往前看，有好女孩要大胆追、要珍惜。记事起就哭过有数的四次，黄花菜就是其中之一！
现在想起来这句话还是很心酸