POJ-1088-滑雪——经典DP
#include"stdio.h"
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int r,c;//r和c分别是行和列
int node[101][101]; //放置每个坐标上的高度
int opt[101][101]; //放置从每个坐标出发的最优解
bool ok(int i,int j)
{
return (i>=1 && i<=r && j>=1 &&j<=c);
}
int dp(int i,int j)
{
int k;
if(opt[i][j]>0) return opt[i][j]; //如果已经计算出,直接返回
for(k=0;k<4;k++) //向四个方向延伸
{
if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
if( node[i+dx[k][j+dy[k]<node[i][j] ) //满足滑雪条件
{
if( opt[i][j]< dp(i+dx[k],j+dy[k])+1 )
opt[i][j]=dp(i+dx[k],j+dy[k])+1;
}
}
return opt[i][j];
}
int main()
{
int max=0,i,j;
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
scanf("%d",&node[i][j]);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
opt[i][j]=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(max<dp(i,j))max=dp(i,j);
printf("%d",max+1); //输出值需要+1,因为在前面的计算中,每个点的初始值都是0
return 0;
}
【后记】
code过程中,几乎任何重复的代码都可以简化,这也是程序中ok()和dx、dy的妙处。
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int r,c;//r和c分别是行和列
int node[101][101]; //放置每个坐标上的高度
int opt[101][101]; //放置从每个坐标出发的最优解
bool ok(int i,int j)
{
return (i>=1 && i<=r && j>=1 &&j<=c);
}
int dp(int i,int j)
{
int k;
if(opt[i][j]>0) return opt[i][j]; //如果已经计算出,直接返回
for(k=0;k<4;k++) //向四个方向延伸
{
if(ok(i+dx[k],j+dy[k])) //如果节点没有超出边界
if( node[i+dx[k][j+dy[k]<node[i][j] ) //满足滑雪条件
{
if( opt[i][j]< dp(i+dx[k],j+dy[k])+1 )
opt[i][j]=dp(i+dx[k],j+dy[k])+1;
}
}
return opt[i][j];
}
int main()
{
int max=0,i,j;
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
scanf("%d",&node[i][j]);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
opt[i][j]=0;
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(max<dp(i,j))max=dp(i,j);
printf("%d",max+1); //输出值需要+1,因为在前面的计算中,每个点的初始值都是0
return 0;
}
【后记】
code过程中,几乎任何重复的代码都可以简化,这也是程序中ok()和dx、dy的妙处。
热门话题 · · · · · · ( 去话题广场 )
- 我们为什么需要书店? 1.9万次浏览
- 解锁我的夏日旅行足迹地图 活动 55.5万次浏览
- 你有哪些保持精力充沛的方法? 1755次浏览
- 你想对高考生们说点什么? 3.5万次浏览
- 哪一刻你真正感觉到了自己身体的存在? 5.8万次浏览
- 我喝过的好喝精酿 新话题 · 4.2万次浏览