我们学校的ACM网站进不去了。。。
滑雪,这个题目是稍微复杂一些的动态规划题,基本思路是先求的一个点上,上下左右上的最优值,然后再做判断。。该题一定要抓住这种思想,不然会很迷惑。
在代码实现的时候,用了一个中间值temp,用来存贮最优解。。。
代码如下:
#include<stdio.h>
#include<string.h>
int s[101][101],map[101][101];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int d[4][2]=
{
{0,1},
{1,0},
{-1,0},
{0,-1}};
int n,m;
int dfs(int x,int y) //计算x,y点上的最大深度,事实上它可以计算出所有他可以到达点上的最优值
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int sum=0;
int temp=0;
int i,x0,y0;
if(s[x][y]!=0)
return s[x][y];
for(i=0;i<4;i++) //从上下左右四个最优值中选择
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
x0=d[i][0]+x;
y0=d[i][1]+y;
temp=1; //最小深度为1。。
if((map[x0][y0]<map[x][y])&&x0>=0&&y0>=0&&x0<n&&y0<m)//满足条件的点,重置temp
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
temp=dfs(x0,y0)+1;
}
if(temp>sum) //更新最大深度
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum=temp;
}
}
s[x][y]=sum; //置最优值
return sum; //返回最优值
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int sum,i,j;
while(scanf("%d %d",&n,&m)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(s,0,sizeof(s));
sum=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dfs(i,j);
}
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j=0;j<m;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(s[i][j]>sum)
sum=s[i][j];
//printf("%d ",s[i][j]);
}
// printf("\n");
}
printf("%d\n",sum);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
这段代码可能是我自己写的,我记得当时我不理解这个,网上找了很多代码来看,结果还是看不懂。。。现在我看着这段代码还是觉得虚,虽然我理解他的意思。。。总结经验我觉得以前没有好好理解这个题目,然后盲目的看代码,结果毁了这个题目!!!以后一定要抓住思路再写代码!!!其实这个题目可以看做是最长不下降子序列扩展到二维的情况!!可能这也是我解决不了这个题目的一个因素,除了思路不清晰外,在写代码的时候直接用最优数组去迭代是不能成功的!!要用到中间变量!!最后总结为:1、盲目看\写代码。。2、经验主义。。
posted on 2010-09-17 10:29
jince 阅读(492)
评论(0) 编辑 收藏 引用