DP-查表法
查表法的前提——
1. 不能循环查询
例如,本题目:查询dp(i,j),需要在内部查询dp(i',j'),可能继续进行递归,但因为递归过程总是沿着海拔降低,故不可能回过头来再次查询dp(i,j)
2. 正确处理递归(查表)终止条件
本题中,如果点(i,j)旁边没有低于它的点,则len[i][j]为0,直接返回
代码:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define N 101
int map[N][N],len[N][N];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int r,c;
//点(i,j)为起始的最长滑行路线长度
int dp(int i,int j)
{
if(len[i][j]!=0)
return len[i][j];
int sub_max=0,s;
for(int t=0;t<4;t++)
{
int temx=i+dir[t][0],temy=j+dir[t][1];
if(temx>=0 && temx<r && temy>=0 && temy<c &&
map[temx][temy]<map[i][j])
{
s=dp(temx,temy);
if(s>sub_max)
sub_max=s;
}
}
len[i][j]=sub_max+1;
return sub_max+1;
}
int main()
{
while(~scanf("%d%d",&r,&c))
{
int mx=-1;
memset(len,0,sizeof(len));
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
scanf("%d",&map[i][j]);
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
len[i][j]=dp(i,j);
if(len[i][j]>mx)
mx=len[i][j];
}
}
printf("%d\n",mx);
}
}
分享到:
相关推荐
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
poj 1000-3000部分代码 网上收集
北大POJ1159-Palindrome 解题报告+AC代码
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码