关键词：
记忆化搜索：
通俗地讲就是搜索的形式，dp的思想
一些搜索难以完成，dp的动态转移方程又不好写的题，就会用到记忆化搜索，利用dp记录路径（相当于为dfs剪枝）用dfs进行模拟。。
啦啦啦啦啦啦，，，，，，，，，好厉害！！！！！！
@ https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1059
弱鸡代码
1 #include <string.h> 2 #include <iostream> 3 #include <stdio.h> 4 using namespace std; 5 int a[4][44], dp[44][44][44][44], num[4], n; 6 bool flag[44]; 7 int dfs(int count) 8 if(dp[num[0]][num[1]][num[2]][num[3]] != -1) 9 return dp[num[0]][num[1]][num[2]][num[3]]; 10 if(count == 5) 11 return dp[num[0]][num[1]][num[2]][num[3]] = 0; 12 int sum = 0; 13 for(int i = 0; i < 4; i++) 14 if(num[i] == n) continue; 15 int color = a[i][num[i]]; 16 num[i] += 1; 17 if(flag[color]) 18 flag[color] = false; 19 sum = max(sum, dfs(count-1)+1); 20 flag[color] = true; 21 22 else 23 flag[color] = true; 24 sum = max(sum, dfs(count+1)); 25 flag[color] = false; 26 27 num[i] -=1 ; 28 29 return dp[num[0]][num[1]][num[2]][num[3]] = sum; 30 31 int main() 32 while(scanf("%d", &n) && n) 33 memset(dp, -1, sizeof(dp)); 34 memset(flag, false, sizeof(flag)); 35 memset(num, 0 ,sizeof(num)); 36 for(int i = 0; i < n; i++) 37 for(int j = 0; j < 4; j++) 38 cin>>a[j][i]; 39 40 41 num[0] = num[1] = num[2] = num[3] = 0; 42 cout<<dfs(0)<<endl; 43 44 return 0; 45
@ http://acm.hdu.edu.cn/showproblem.php?pid=1078
给定一个n*n的地图，最多只能走k步并且保证下一个点的值大于原来的点，求可以得到的最大值
开始故意用纯dfs试了下果然超时。。。。。
垃圾代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int a[105][105], dp[105][105], n, m; 6 int dir[4][2] = 0, 1, 1, 0, 0, -1, -1, 0; 7 int dfs(int r, int c) 8 int ma = 0; 9 if(dp[r][c]<0) 10 for(int j = 1; j <= m; j++) 11 for(int i = 0; i < 4; i++) 12 int rx = r + dir[i][0]*j; 13 int cx = c + dir[i][1]*j; 14 if(rx >=0 && rx < n && cx >= 0 && cx <n && a[rx][cx] > a[r][c]) 15 ma = max(ma,dfs(rx, cx)); 16 17 18 19 dp[r][c] = ma + a[r][c]; 20 21 return dp[r][c]; 22 23 int main() 24 while(scanf("%d %d", &n, &m)) 25 if(n == -1 && m == -1) break; 26 else 27 for(int i = 0; i < n; i++) 28 for(int j = 0; j < n; j++) 29 scanf("%d", &a[i][j]); 30 dp[i][j] = -1; 31 32 33 printf("%d\n", dfs(0, 0)); 34 35 36 return 0; 37
@ 玲珑杯：：：：：：：
http://www.ifrog.cc/acm/problem/1032
n个球放在m个盒子里面，要求放最多球的盒子数唯一，（可以放零个球）， 求最多的放法
明显的记忆化搜索
垃圾代码
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 #define ll long long 5 const ll mod = 998244353; 6 ll dp[505][505], n, m, num = 0; 7 ll dfs(ll he, ll qiu, ll ma) 8 if(he == 0) 9 if(qiu == 0) return 1; 10 else return 0; 11 12 if(dp[he][qiu]) return dp[he][qiu]; 13 ll mam = 0; 14 for(int i = 0; i < ma && i <=qiu; i++) 15 mam += dfs(he-1, qiu-i, ma); 16 mam %= mod; 17 18 dp[he][qiu] = mam; 19 return mam; 20 21 int main() 22 cin>>n>>m; 23 for(int i = n; i >=0; i--) 24 memset(dp, 0, sizeof(dp)); 25 num += dfs(m-1, n-i, i); 26 num %= mod; 27 28 cout<<num*m%mod<<endl; 29 return 0; 30
@ http://acm.hdu.edu.cn/showproblem.php?pid=1978
啦啦啦啦啦， 1A的感觉真是太爽了！！！可能这就是坚持的理由，，经过拼搏换来的快乐才是最大的快乐！！！！
从（0， 0） 点到（n-1， m-1） 点一共有多少种走法（只可以向右向下走）
1 #include <iostream> 2 using namespace std; 3 #define ll long long 4 const int mod = 10000; 5 int a[105][105], dp[105][105], n, m, t; 6 int dir[2][2] = 0, 1, 1, 0; 7 int dfs(int r, int c, int sum) 8 if(r == n-1 && c == m-1) return 1; 9 ll cot = 0; 10 if(dp[r][c] < 0) 11 for(int i = 0; i <= sum; i++) 12 for(int j = 0; j <= sum - i; j++) 13 if(i == 0 && j == 0) continue; 14 int rx = r + i; 15 int cx = c + j; 16 if(rx >= 0 && rx < n && cx >= 0 && cx < m) 17 cot += dfs(rx, cx, a[rx][cx]); 18 cot %= mod; 19 20 21 22 dp[r][c] = cot; 23 24 return dp[r][c]; 25 26 int main() 27 cin>>t; 28 while(t--) 29 cin>>n>>m; 30 for(int i = 0; i < n; i++) 31 for(int j = 0; j < m; j++) 32 cin>>a[i][j]; 33 dp[i][j] = -1; 34 35 36 cout<<dfs(0, 0, a[0][0])<<endl; 37 38 return 0; 39
-------------------------------------------
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1455
关键在于跳的次数不会很大
1 #include "iostream" 2 #include <string.h> 3 using namespace std; 4 5 const int maxn = 30009; 6 int sum[maxn][777], num[maxn], n, d, num2[maxn]; 7 bool vis[maxn][777]; 8 9 int dd(int pos, int l) 10 if(pos > 30000) return 0; 11 if(sum[pos][l] != -1) return sum[pos][l]; 12 sum[pos][l] = num[pos]; 13 int cnt = 0; 14 cnt = max(cnt, dd(pos+l+1-300+d, l+1)); 15 cnt = max(cnt, dd(pos+l-300+d, l)); 16 if(l+d-300 > 1) cnt = max(cnt, dd(pos+l-300-1+d, l-1)); 17 sum[pos][l] += cnt; 18 return sum[pos][l]; 19 20 21 int main() 22 int x; 23 scanf("%d%d", &n, &d); 24 for(int i = 0; i < n; ++i) 25 scanf("%d", &x); 26 num[x] ++; 27 28 memset(sum, -1, sizeof(sum)); 29 printf("%d\n", dd(d, 300)); 30 return 0; 31
只有不断学习才能进步！
hdu6468（记忆化搜索）(代码片段)
zyb的面试TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):695 AcceptedSubmission(s):254ProblemDescription今天zyb参加一场面 查看详情
codeforces919d.substring（记忆化搜索）(代码片段)
DescriptionYouaregivenagraphwithnnodesandmdirectededges.Onelowercaseletterisassignedtoeachnode.Wedefineapath’svalueasthenumberofthemostfrequentlyoccurringletter.Forexample,iflettersonapathare“abaca”,t 查看详情
牛老板(记忆化搜索&贪心)(代码片段)
牛老板(记忆化搜索&贪心)贪心，考虑优先选较大的。因为满足倍数关系，但需要考虑是否整除。所以每次选较大的和次大的。//Problem:牛老板//Contest:NowCoder//URL:https://ac.nowcoder.com/acm/contest/11177/C//MemoryLimit:524288MB//TimeLimit:4... 查看详情
kingxmagicspells期望dp(记忆化搜索)(代码片段)
Usedas:DivisionOne-LevelTwo:Value500SubmissionRate281/941(29.86%)SuccessRate226/281(80.43%)HighScorewatafor473.56points(6mins47secs)AverageScore323.08(for226correctsubmissions)AstheXORoperationinvolve 查看详情
2328.网格图中递增路径的数目(记忆化搜索)(代码片段)
2328.网格图中递增路径的数目(记忆化搜索)原理矩阵的四周扩散，也可以记忆化dp。时间复杂度：O(nm)O(nm)O(nm)classSolutionpublic:intcountPaths(vector<vector<int>>&a)intn=a.size(),m=a[0].size();vector<vecto 查看详情
题解滑雪luogu1434记忆化搜索(代码片段)
记忆化搜索入门题题目Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。... 查看详情
hdu-5001walk（概率dp+记忆化搜索）(代码片段)
Walk IusedtothinkIcouldbeanything,butnowIknowthatIcouldn‘tdoanything.SoIstartedtraveling. Thenationlookslikeaconnectedbidirectionalgraph,andIamrandomlywalkingonit.ItmeanswhenIamatnodei,Iwill 查看详情
poj1579functionrunfun记忆化搜索入门(代码片段)
题目传送门：http://poj.org/problem?id=1579FunctionRunFunTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 20560 Accepted: 10325DescriptionWeallloverecursion!Don‘twe? 查看详情
hdu1078fatmouseandcheese（记忆化搜索）(代码片段)
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1078FatMouseandCheeseTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):13356 &n 查看详情
gym101933e（记忆化搜索）(代码片段)
用每个人的血量作为状态去搜索T飞，考虑题解中更好的搜索方式：每种血量有多少个人作为状态。这样会减去很多重复的状态，因为只要乘一下就得到了所有相同情况的和。虽然我不会算，但是直观感受起来复杂度比较优秀。#i... 查看详情
hdu1078fatmouseandcheese记忆化搜索(代码片段)
...索做，但是在搜索的过程中，我们应该加入dp的思想，即记忆化搜索，对于已经搜索过的点，我们就可以不用重复搜索了，直接调用它的值就行。# 查看详情
loppinha,theboywholikessopinhagym-101875e(dp,记忆化搜索)(代码片段)
...种情况下应该是要把第二个和第四个拿掉来最小所以要用记忆化搜索或dp；记忆化搜索 #inc 查看详情
uoj167元旦老人与汉诺塔（记忆化搜索）(代码片段)
QwQ太懒了，题目直接复制uoj的了QwQ这个题可以说是十分玄学的一道题了首先可以暴搜，就是(dfs)然后模拟每个过程是哪个柱子向哪个柱子移动不多解释了，不过实现起来还是有一点点难度的直接上代码吧#include<iostream>#include&l... 查看详情
poj2704pascal'stravelsdfs记忆化搜索(代码片段)
题目传送门：http://poj.org/problem?id=2704Pascal‘sTravelsTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 5535 Accepted: 2500DescriptionAnnxngameboardispopulatedwithinteg 查看详情
uva-11761-马尔可夫/记忆化搜索(代码片段)
...期望挑选次数。 f[i]=1/(m1+m2)*(SUMf[i]+SUMf[i/x])+1,化简后记忆化搜索就好了，筛素数的时候要保存所有的素数所以不能根号优化。 1#include<iostream& 查看详情
函数记忆化搜索模型(代码片段)
问题描述：计算ackerman函数值:Ack(m,n)if(m==0)n+1;if(n==0)ack(m-1,1) if(m&&n>0)ack((m-1),ack(m,n-1))输入格式：从文件ackerman.in读入数据，第一行为两个数，即M和N，其中0<=M<=3，0<=N<=11。 输出格式：向文件ackerman.out输 查看详情
hdu多校9rikkawithnashequilibrium（记忆化搜索/dp）(代码片段)
RikkawithNashEquilibriumTimeLimit:10000/5000MS(Java/Others) MemoryLimit:524288/524288K(Java/Others)TotalSubmission(s):1460 AcceptedSubmission(s):591Proble 查看详情
滑雪记忆化搜索简单模型(代码片段)
滑雪是一项非常刺激的运动，为了获得速度，滑雪的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。给出一个由二维数组表示的滑雪区域，数组的数字代表各点的高度。请你找出这个区域中... 查看详情