思维导图
记忆化搜索图示:
剪枝和优化解释
例题讲解:
【天下第一】
#include <bits/stdc++.h> using namespace std; int t , x , y , mod;//定义 int book[10010][10010]; int rem(int x,int y) { if(book[x][y] == -1){ return -1; } if(book[x][y]){ return book[x][y];//如果之前搜到过 } book[x][y]=-1; //标记 if(!x){ return book[x][y] = 1; } if(!y){ return book[x][y]=2; } int num=(x+y)%mod;//num=处理后的x return book[x][y]=rem(num,(num+y)%mod);//记忆 } int main(){ scanf("%d %d",&t,&mod);//读入 for(int i = 0 ; i < t ; i++){ scanf("%d %d",&x,&y); int ans = rem(x , y);//搜索 //输出 if(ans == -1){ cout << "error\n"; } else if(ans == 1){ cout << "1\n"; } else{ cout << "2\n"; } } return 0; }
[滑雪]
#include<bits/stdc++.h> using namespace std; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int n , m , a[201][201] , s[201][201] , ans; bool use[201][201]; int dfs(int x,int y){ if( s[x][y] ){ return s[x][y];//记忆 } s[x][y]=1;//题目中答案是有包含这个点的 for(int i = 0 ; i < 4 ; i++){ int xx = dx[i] + x; int yy = dy[i] + y;//四个方向 if(xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy]){ dfs(xx,yy); s[x][y] = max(s[x][y],s[xx][yy]+1); } } return s[x][y]; } int main() { scanf("%d%d",&n,&m);//同题目的R,C for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ; j++){ scanf("%d" , &a[i][j]); } } for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ; j++){ ans = max(ans,dfs(i,j));//取最大值 } }//找从每个出发的最长距离 printf("%d",ans); return 0; }
[蚂蚁打工]
#include<bits/stdc++.h> using namespace std; int n,a[20][20],vis[20],b[20],ans=1600; void dfs(int t,int sum){ if(sum>ans) return; //剪枝 if(t==n+1){ // ans=min(ans,sum); return; } //坑没填完 for(int i=1;i<=n;i++){//第t只蚂蚁能选1~n的任务 //任务必须没有被选掉 if(vis[i]==0){ //第t只蚂蚁选了任务i vis[i]=1; dfs(t+1,sum+a[t][i]);//轮到下一只蚂蚁 vis[i]=0; } } } int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; //选任务 dfs(1,0);//第一只蚂蚁去选任务 cout<<ans; return 0; }
程序阅读题:八皇后
总结