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.8万次浏览
- 你所知道的特别的酒文化 8.8万次浏览
- 如何快速融入一个新城市的生活? 58.3万次浏览
- 每座城市都有一首属于它的歌 10.0万次浏览
- 作为一个写作者,你都读什么书? 8.5万次浏览
- 陷入饮食安全担忧怪圈的时刻 3.6万次浏览