注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1078 FatMouse and Cheese & hdu 1978 How many ways & hdu 1428 漫步校园(记忆化搜索)  

2013-08-04 13:45:13|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1078
这三题都是记忆化搜索的典型题。

hdu 1078 FatMouse and Cheese
给出一个n*n的矩阵,每个格子上的数代表奶酪数,起始位置在(0, 0)。每次可以水平或者垂直走,最多走k个单位,并且目标位的奶酪数要比当前位的多。每次到一个地方就把当前的奶酪都吃掉,问最多可以吃掉多少奶酪。
从(0,0)开始搜索,能获取的最多奶酪数等于当前奶酪数+下一步能搜到的最多奶酪数。

/*
* fudq.cpp
*
* Created on: 2013-08-04
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=110;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

int n,k,f[N][N],ans[N][N];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

int dfs(int x,int y)
{
if(ans[x][y] != -1)
return ans[x][y];
int s=0;
for(int i=0;i<4;i++)
for(int j=1;j<=k;j++)
{
int tx=x+dir[i][0]*j;
int ty=y+dir[i][1]*j;
if(tx>=0 && ty>=0 && tx<n && ty<n && f[tx][ty]>f[x][y])
s=max(s,dfs(tx,ty));
}
ans[x][y]=s+f[x][y];
return ans[x][y];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==-1 && k==-1)
break;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&f[i][j]);
memset(ans,-1,sizeof(ans));
printf("%d\n",dfs(0,0));
}
return 0;
}


hdu 1978 How many ways
控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m),机器人一开始在棋盘的起始点并有起始点所标有的能量,只能往下或者右走,走一次消耗一单位能量,不能停留原地,当选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。(机器人不一定要走到没能量了才停止,可以在中途停下换路径)问有多少种情况。
可以用记忆化搜索或者dp解决。

记忆化搜索:

/*
* fudq.cpp
*
* Created on: 2013-08-02
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=110;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

int n,m,f[N][N],ans[N][N];

int dfs(int x,int y)
{
if(x>n || x<0 || y>m || y<0)
return 0;
if(x==n-1 && y==m-1)
return 1;
if(ans[x][y] != -1)
return ans[x][y];
int s=0;
for(int i=0;i<=f[x][y];i++)
for(int j=0;j+i <= f[x][y];j++)
{
if(i==0 && j==0)
continue;
s=(s+dfs(x+i,y+j))%10000;
}
ans[x][y]=s;
return s;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&f[i][j]);
memset(ans,-1,sizeof(ans));
printf("%d\n",dfs(0,0));
}
return 0;
}


dp:
把当前值加到当前能到达的位置上。

/*
* fudq.cpp
*
* Created on: 2013-08-02
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=110;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

int n,m,f[N][N],ans[N][N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&f[i][j]);
memset(ans,0,sizeof(ans));
ans[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int t=f[i][j];
for(int p=0;p<=t;p++)
for(int q=0;q+p<=t;q++)
{
if((p==0 && q==0) || i+p >= n || j+q >=m)
continue;
ans[i+p][j+q]+=ans[i][j];
ans[i+p][j+q]%=10000;
}
}
printf("%d\n",ans[n-1][m-1]);
}
return 0;
}


hdu 1428 漫步校园
n*n的矩阵,每个点表示过这个点需要的时间,上下左右四个方向走,问从(1,1)寝室到(n,n)机房有多少种走法。条件是从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。
还是挺容易想的,先bfs求出终点到各点的最短距离,然后记忆化搜索,条件是目标位置离终点的距离小于当前位置离终点的距离。

/*
* fudq.cpp
*
* Created on: 2013-08-04
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=60;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

struct Node{
int x,y;
};
int n,f[N][N],dis[N][N];
LL ans[N][N];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void bfs()
{
queue<Node>Q;
dis[n][n]=f[n][n];
Node t,p;
t.x=n;t.y=n;
Q.push(t);
while(!Q.empty())
{
t=Q.front();
Q.pop();
for(int i=0;i<4;i++)
{
p.x=t.x+dir[i][0];
p.y=t.y+dir[i][1];
if(t.x>0 && t.y>0 && t.x<=n && t.y<=n && dis[p.x][p.y]>dis[t.x][t.y]+f[p.x][p.y])
{
dis[p.x][p.y]=dis[t.x][t.y]+f[p.x][p.y];
Q.push(p);
}
}
}
}

LL dfs(int x,int y)
{
if(ans[x][y] != -1)
return ans[x][y];
if(x==n && y==n)
return 1;
LL s=0;
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx>0 && ty>0 && tx<=n && ty<=n && dis[tx][ty]<dis[x][y])
s+=dfs(tx,ty);
}
ans[x][y]=s;
return s;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&f[i][j]);
dis[i][j]=INF;
}
bfs();
memset(ans,-1,sizeof(ans));
printf("%I64d\n",dfs(1,1));
}
return 0;
}


  评论这张
 
阅读(167)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018