dfs+dp思想的结合------hdu1078

首先是题目的意思:

从一个正方形的0,0点开始走,只能横着走,竖着走,最多走k步,下一个点的数一定要比当前这个点的值大,每走一步,就加上下一个点的数据,问数据最大能有多少。

首先遇到这种题目,走来走去的,一开始想到的是搜索,但是搜索我们搜的很多是路径,能走到那个点的最短路,但是这道题目不一样。

首先要注意的一点是,如果没有条件的搜索,那就是枚举。只有搜遍了才能得到最后的解。

1s题,只是搜的话肯定TLE了。

所以我们想到的自然就是dp了。dp的好处是什么?就是能减少不必要的搜索。用已知的结果减少当前路径搜索的时间。

几个要点:

1、只能从0,0开始走,所以已经减少了很多复杂了,不要傻乎乎的全部循环。

2、注意dfs时候的边界判断。

3、更新值时不要忘记加上当前自己的值。

状态转移方程

dp[][] = max(所有可以从当前点走到的点的dfs的结果集)

初始值肯定是0没问题

最后dp【0】【0】就是结果了。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm> using namespace std;
/*dfs+dp,hdu1078*/ int maps[][];//用来保存原数据
int dp[][];//dp数组
int k;//最多走的步数
int n;//区域大小 int update(int x,int y)
{
int i,j;
int fromX,toX;
int fromY,toY;
int maxTemp=;
int temp; //判断边界条件
if(dp[x][y])
return dp[x][y]; if(x-k < )
fromX = ;
else
fromX = x-k; if(x+k >= n)
toX = n-;
else
toX = x+k; if(y-k < )
fromY = ;
else
fromY = y-k; if(y+k >= n)
toY = n-;
else
toY = y+k; for (i = fromX; i <= toX; i++)
{
if(i!=x && maps[i][y] > maps[x][y])
{
temp = update(i,y);
if(temp > maxTemp)
maxTemp = temp;
}
} for (j = fromY; j <= toY; j++)
{
if(j!=y && maps[x][j] > maps[x][y])
{
temp = update(x,j);
if(temp > maxTemp)
maxTemp = temp;
}
} dp[x][y] = maxTemp + maps[x][y];
return dp[x][y];
} int main()
{
int i,j;//循环变量
int maxNumber=;//记录结果 while (true)
{
cin>>n>>k;
if(n==- && k==-)
break;
memset(dp,,sizeof(dp));
//输入数据
for (i = ; i < n; i++)
for (j = ; j < n; j++)
cin>>maps[i][j]; //只能从0.0点开始走
maxNumber = update(,); cout<<maxNumber<<endl;
} return ;
}
上一篇:zabbix监控交换机状态


下一篇:SharePoint 2013 使用JavaScript对象模型配置智能提示