记忆化搜索
算法上依然是搜索的流程，但是搜索到的一些解，用动态规划的那种思想和模式作一些保存。一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。—[百度百科]
POJ 1088 滑雪
链接
滑雪
题意
有一个R*C的矩形区域，区域(i,j)的高度为h[i,j]
一个人可以从某个点滑向上下左右相邻四个点之一，
当且仅当高度减小，求最长区域的长度
分析
记忆化搜索
若与点a相邻的点b高度比a大，则从b可以到a
dp[i][j]为以(i,j)为起点最长区域的长度
dp[i][j]=max(上下左右四个点能到(i,j)的长度)+1
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<stdio.h>
#include<algorithm>
using namespace std;
int h[105][105],dp[105][105],r,c;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,-1,1};
bool judge(int row,int col)
{
if(row>=1&&row<=r&&col>=1&&col<=c)
return true;
return false;
}
int dfs(int x,int y)
{
if(dp[x][y])
return dp[x][y];
dp[x][y]=1;
for(int k=0;k<4;k++){
int row=x+dx[k];
int col=y+dy[k];
if(judge(row,col)&&h[x][y]>h[row][col])
dp[x][y]=max(dp[x][y],dfs(row,col)+1);
}
return dp[x][y];
}
int main()
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++){
scanf("%d",&h[i][j]);
dp[i][j]=0;
}
int ans=-1;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
ans=max(ans,dfs(i,j));
printf("%d\n",ans);
return 0;
}
|
Hdu 1078 FatMouse and Cheese
链接
FatMouse and Cheese
题意
有n*n个洞，每个洞都藏有一定量的奶酪，有一只老鼠初始在(0,0)点
它每次可以从所在地A水平或垂直方向最多走k步到达B，且B的奶酪值比A大
它可以吃掉B处的奶酪，求它最多可以吃多少奶酪
分析
记忆化搜索
dp[i][j]为从(0,0)点出发到(i,j)点能吃的最大奶酪值，则(i,j)可由四个方向到达
因为起点为(0,0)点，但终点未知，所以可以以(0,0)点为终点逆向dfs
注：每次必须朝水平或垂直一个方向走最多k步，而不是每次可以拐弯
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=105;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int n,k,edge[N][N],dp[N][N];
bool judge(int row,int col)
{
if(row>=1&&row<=n&&col>=1&&col<=n)
return true;
return false;
}
int dfs(int x,int y)
{
if(dp[x][y])
return dp[x][y];
int ans=0;
for(int i=1;i<=k;i++){
for(int j=0;j<4;j++){
int row=x+dx[j]*i;
int col=y+dy[j]*i;
if(judge(row,col)&&edge[x][y]<edge[row][col])
ans=max(ans,dfs(row,col));
}
}
dp[x][y]=ans+edge[x][y];
return dp[x][y];
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF){
if(n==-1&&k==-1)
break;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&edge[i][j]);
memset(dp,0,sizeof(dp));
dfs(1,1);
printf("%d\n",dp[1][1]);
}
return 0;
}
|
Hdu 1428 漫步校园
链接
漫步校园
题意
有一个n*n的方格，走到每个方格都需要一定时间
先要从(0,0)点走到(n,n)点，每次可以走到上下左右相邻的点
若从A点到B点，则从B出发存在一条到终点的路比从A出发的任意一条到终点的路都近
求从(0,0)点走到(n,n)点有多少条路
分析
本题实质是求从起点到终点的最短路的条数
可以先用SPFA求以(n,n)点为原点到各点的最短路径
再用记忆化搜索逆向求(n,n)点到(0,0)点的最短路径长度
正向求(0,0)到(n,n)TLE了，不懂为什么…
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<stdio.h>
#include<queue>
#include<string.h>
const int N=60;
const int INF=999999;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
using namespace std;
int n,dis[N][N],edge[N][N];
long long dp[N][N];
bool judge(int row,int col)
{
if(row>=1&&row<=n&&col>=1&&col<=n)
return true;
return false;
}
void SPFA()
{
bool vis[N][N];
queue<int> q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=INF;
vis[i][j]=false;
}
}
dis[n][n]=edge[n][n];
q.push(n);
q.push(n);
vis[n][n]=true;
while(!q.empty()){
int x=q.front();
q.pop();
int y=q.front();
q.pop();
vis[x][y]=false;
for(int k=0;k<4;k++){
int row=x+dx[k];
int col=y+dy[k];
if(judge(row,col)&&dis[x][y]+edge[row][col]<dis[row][col]){
dis[row][col]=dis[x][y]+edge[row][col];
if(!vis[row][col]){
q.push(row);
q.push(col);
vis[row][col]=true;
}
}
}
}
}
long long dfs(int x,int y)
{
if(dp[x][y])
return dp[x][y];
for(int k=0;k<4;k++){
int row=x+dx[k];
int col=y+dy[k];
if(judge(row,col)&&dis[row][col]<dis[x][y])
dp[x][y]+=dfs(row,col);
}
return dp[x][y];
}
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&edge[i][j]);
SPFA();
memset(dp,0,sizeof(dp));
dp[n][n]=1;
dfs(1,1);
printf("%I64d\n",dp[1][1]);
}
return 0;
}
|