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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2110Mountain Walking题解  

2014-03-25 20:39:52|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

山行

BY   LGS

题目大意:求从一个N*N的矩阵左上角到左下角一条最高值与最小值差值最小的最短路.

 

题解:显然最短路一定是往右或者往下走.一开始我写了F[X][Y]的记忆化搜索WA,因为你每次保证它们的差最小不一定是最优的,因为相同的最大值下的状态会扩展不到.于是我写了一个三维的记忆化,F[X][Y][J]表示到X,Y这个点以J为最大值下的最小值,显然这样满足最优子结构了,使最小值最大即可.因为差值要尽量小.

总结:记忆化搜索

 

 

代码:
#include<cstdio>
#include<cstring>
#define maxn 120
#define maxx 99999999
using namespace std;
int i,j,n,k,ans,m;
int a[maxn][maxn],f[maxn][maxn][maxn];
const int han[]={0,1,-1,0,0};
const int lie[]={0,0,0,1,-1};
int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a>b)?b:a;} 
void dfs(int x,int y,int ma,int mi)
 {
 int i;
 f[x][y][ma]=mi;
 for (int i=1;i<=4;i++)
            {
             int w=x+han[i];int ww=y+lie[i];
            if ((w>0)&&(ww>0)&&(w<=n)&&(ww<=n))
             {int u=max(a[w][ww],ma);int uu=min(a[w][ww],mi);
              if (f[w][ww][u]<uu) dfs(w,ww,u,uu);
              } 
            }
 }
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++)
  for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
memset(f,-1,sizeof(f));
dfs(1,1,a[1][1],a[1][1]);
ans=maxx;
for (i=0;i<=110;i++)if (f[n][n][i]!=-1)
            ans=min(ans,i-f[n][n][i]);
printf("%d",ans);
//for(;;);
return 0; 
}                                                               
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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