poj 1088 动态规划

#include <iostream>
#include <string.h>
using namespace std; int ans[][];//存储当前位置能得到的最优解
int map[][];//存储当前位置的元素值
int dir[][]={,,,,-,,,-};//四个方向,右,上,左,下
int N,M;
int max(int a,int b)
{
return a>b?a:b;
}
int dp(int i,int j)//得到[i,j]位置的最优解
{
if(ans[i][j]>) return ans[i][j];
//寻找四个方向的局部满足要求的最优解
int t,tempi,tempj;
int maxn=;
for(t=;t<;t++)
{
tempi=i+dir[t][];
tempj=j+dir[t][];
if(tempi>&&tempi<=N&&tempj>&&tempj<=M) //不可越界
{
if(map[tempi][tempj]<map[i][j])//低于[i,j]
maxn=max(maxn,dp(tempi,tempj));
}
}
return ans[i][j]=maxn+;
}
int main()
{
while(cin >>N >> M)
{
int answer=;
int i,j;
for(i=;i<=N;i++)
{
for(j=;j<=M;j++)
{
cin >> map[i][j];
}
}
memset(ans,,sizeof(ans));
for(i=;i<=N;i++)
{
for(j=;j<=M;j++)
{
ans[i][j]=dp(i,j);//得到[i,j]位置的最优解
answer=max(answer,ans[i][j]);//更新整体最优解
}
}
cout << answer;
}
return ;
}
上一篇:BZOJ1433 ZJOI2009 假期的宿舍 二分图匹配


下一篇:bzoj1433:[ZJOI2009]假期的宿舍