http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
虽然对搞ACM的人很简单,但是对我这种非专业人士而言也有点难度,而且是第一次写记忆化搜索的dp。
#include<stdio.h>
int dp(int row,int col);
int calculated[100][100],r,c,min_x,min_y;
int sum[100][100],board[100][100],result;
int dx[4] = {0,0,1,-1} , dy[4] = {1,-1,0,0};
int main()
{
int i,j,k,min = 10001;
scanf("%d%d",&r,&c);
for (i = 0;i < 100;i++)
for (j = 0;j < 100;j++)
{ sum[i][j] = 1;
calculated[i][j] = 0;
}
for (i = 0;i < r;i++)
for (j = 0;j < c;j++)
{
scanf("%d",&board[i][j]);
if (board[i][j] < min)
{
min = board[i][j];
min_x = i;
min_y = j;
}
}
result
= 0;
for (i = 0;i < r;i++)
for (j = 0;j < c;j++)
{
dp(i,j);
if (result < sum[i][j])
result
= sum[i][j];
}
printf("%d\n",result);
return 0;
}
int dp(int row,int col)
{
int i,j,temp_row,temp_col,temp_sum;
if (calculated[row][col])
return
sum[row][col];
else
{
for (i = 0;i < 4;i++)
{
temp_row = row + dx[i];
temp_col
= col + dy[i];
if(temp_row >= 0 && temp_row < r
&& temp_col >= 0 && temp_col < c
&& board[temp_row][temp_col] > board[row][col])
{
temp_sum = dp(temp_row,temp_col) + 1;
if (temp_sum > sum[row][col])
sum[row][col] = temp_sum;
}
}
calculated[row][col] = 1;
return sum[row][col];
}
}