poj 1088(DP+递归)
2024-10-20 11:27:50
这题状态方程很容易得到:DP[i][j] = max(DP[i-1][j],DP[i+1][j],DP[i][j-1],DP[i][j+1]) + 1
难点在于边界条件和剪枝,因为这方程的条件是点在map里,且只有递增关系才会变化,如果用循环的话要判断递增,所以用递归比较方便
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define debug printf("!\n")
#define INF 10000
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long int n,m,V;
int dp[][],map[][]; int f(int i,int j)
{
if(dp[i][j]!=)
return dp[i][j];
int w,s,a,d;
if(i->=)
{
if(map[i-][j]<map[i][j]) s=f(i-,j)+;
else s=;
}
else s=;
if(i+<=n)
{
if(map[i+][j]<map[i][j]) w=f(i+,j)+;
else w=;
}
else w=;
if(j->=)
{
if(map[i][j-]<map[i][j]) a=f(i,j-)+;
else a=;
}
else a=;
if(j+<=m)
{
if(map[i][j+]<map[i][j]) d=f(i,j+)+;
else d=;
}
else d=; int max1 = max(w,s);
int max2 = max(a,d);
return max(max1,max2); } int main()
{
int i,j,t;
while(~sf("%d%d",&n,&m))
{
mem(dp,);
dp[][] =;
for(i=;i<=n;i++)
{
for(j = ;j<=m;j++)
sf("%d",&map[i][j]);
}
int max = ;
for(i=;i<=n;i++)
{
for(j = ;j<=m;j++)
{
dp[i][j]=f(i,j);
if(max<dp[i][j]) max = dp[i][j];
}
}
pf("%d\n",max); }
}
最新文章
- 使用C#的反射机制读取类的字段名称及值
- 【代码笔记】iOS-短信分享
- 在Visio2010中修改默认字体的大小
- jython 2.7 b3发布
- Java堆
- 微信利用PHP创建自定义菜单的方法
- 解决mysql中文乱码(总)
- JavaServer Faces 2.2 requires Dynamic Web Module 2.5 or newer
- TCP/IP详解学习笔记(3)-IP协议,ARP协议,RARP协议
- C对字符串的部分操作
- 浏览器扩展系列————异步可插入协议(pluggable protocol)的实现
- 漏洞预警 | Apache Struts2 曝任意代码执行漏洞 (S2-045)
- Java8学习(3)- Lambda 表达式
- Shiro入门这篇就够了【Shiro的基础知识、回顾URL拦截】
- Git分支合并冲突解决
- js中call()的用法
- 「SCOI2015」国旗计划 解题报告
- 远程桌面 把explorer关掉了
- AlarmManager守护服务和隐藏桌面图标
- shell截取字符串的一些简单方法