hdu 1208+hdu 1619(记忆化搜索）

贴几道记忆化搜索题：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1208

思路：记忆话搜索，不过有一个trick就是如果map[i][j]==0并且不是终点，就直接返回0了。如果map[ i ][ j ]表示跳几格 dp[ i ][ j ] 表示有几种条法 , 其实就是一个子状态继承问题，如果map[ i ][ j ]为k, 那么 dp [ i+k ][ j ] 和dp[i][j+k] 就可以增加 dp[ i ][ j ]种跳跃方法了。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 #define MAXN 44
 7 int map[MAXN][MAXN];
 8 char str[MAXN];
 9 ll dp[MAXN][MAXN];
10 int n;
11 
12 ll dfs(int x,int y){
13     if(x==n&&y==n){
14         return (ll)1;
15     }
16     if(map[x][y]==0)return 0;
17     if(dp[x][y])return dp[x][y];
18     for(int flag=0;flag<=1;flag++){
19         int xx,yy;
20         if(flag){xx=x,yy=y+map[x][y];}
21         else {xx=x+map[x][y],yy=y;}
22         if(xx>=1&&xx<=n&&yy>=1&&yy<=n){
23             dp[x][y]+=dfs(xx,yy);
24         }
25     }
26     return dp[x][y];
27 }
28 
29 
30 int main(){
31     while(~scanf("%d",&n)&&n!=-1){
32         for(int i=1;i<=n;i++){
33             scanf("%s",str+1);
34             for(int j=1;j<=n;j++){
35                 map[i][j]=str[j]-'0';
36             }
37         }
38         memset(dp,0,sizeof(dp));
39         ll ans=dfs(1,1);
40         printf("%I64d\n",ans);
41     }
42     return 0;
43 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1619

思路：搜索结果取三个方向的最小值即可，最后打印行号比较麻烦，就从头开始找，如果有dp[x][y]==dp[i][y+1]+map[x][y],说明是下一个行号，而i(0-n-1)保证了字典序。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 222
 6 #define inf 1<<30
 7 int map[MAXN][MAXN];
 8 int dp[MAXN][MAXN];
 9 int n,m,len;
10 int path[MAXN];
11 
12 
13 int dfs(int x,int y){
14     if(dp[x][y]!=inf)return dp[x][y];
15     if(y==m-1)return dp[x][y]=map[x][y];
16     int ans=min(min(dfs((x-1+n)%n,y+1),dfs(x,y+1)),dfs((x+1)%n,y+1));
17     return dp[x][y]=ans+map[x][y];
18 }
19 
20 
21 void Solve(int x,int y){
22     path[len++]=x;
23     if(y==m-1)return ;
24     int x1=(x-1+n)%n,x2=x,x3=(x+1)%n;
25     for(int i=0;i<n;i++){
26         if(dp[x][y]==dp[i][y+1]+map[x][y]&&(i==x1||i==x2||i==x3)){
27             Solve(i,y+1);
28             return ;
29         }
30     }
31 }
32 
33 int main(){
34     while(~scanf("%d%d",&n,&m)){
35         memset(dp,0,sizeof(dp));
36         for(int i=0;i<=n;i++)
37             for(int j=0;j<=m;j++)
38                 dp[i][j]=inf;
39         for(int i=0;i<n;i++)
40             for(int j=0;j<m;j++)
41                 scanf("%d",&map[i][j]);    
42         int ans=inf,pos;
43         for(int i=0;i<n;i++){
44             if(dfs(i,0)<ans){ans=dp[i][0],pos=i;}
45         }
46         len=0;
47         Solve(pos,0);//从第一列的第pos行往后找路径（dp[pos][0]即为最小值）
48         printf("%d",path[0]+1);
49         for(int i=1;i<len;i++){
50             printf(" %d",path[i]+1);
51         }
52         printf("\n%d\n",ans);
53     }
54     return 0;
55 }