【ダイナミックプランニング】練習問題-スキー問題

原題リンク-スキー
タイトルの説明
マイケルはスキーが好きです.これはおかしくない.スキーは確かに刺激的だからだ.しかし、速度を得るためには、滑る領域を下に傾けなければなりません.そして、坂の底に滑ると、再び上り坂を登ったり、リフトを待ったりしなければなりません.マイケルは1つのエリアの中で最も長い滑り坂を知りたいと思っています.領域は2 D配列で与えられます.配列の各数値は、点の高さを表します.次に例を示します.
1 2 3 3 4 5 16 17 19 6 15 24 25 20 7 14 23 22 21 8 13 11 10 9人は、ある点から上下左右に隣接する4つの点の1つにスライドすることができ、高さが減少する場合にのみ.上記の例では、1つの実行可能な勾配は2424−1717−1616−11(2424から11で終了)である.もちろん2525-2424-2323-ldots...-33-22-11はもっと長いです.実は、これは一番長いです.
入力フォーマット
入力された第1の動作は、領域の2次元配列の行数RRおよび列数CCを表す.以下はRR行で、行ごとにCC個の数があり、高さを表します(2つの数字の間に11個のスペース間隔があります).
出力フォーマット
出力領域で最も長い勾配の長さ.
入出力サンプル入力＃15 5 1 1 2 3 4 16 17 18 16 15 24 25 20 7 14 23 22 21 8 13 11 10 9出力＃125
コードの問題解この問題の90パーセントは完全に自分で書いたので、唯一合格しなかったのは、タイムアウトしたので、問題解を参考にして直して合格しました.自分で書いた部分はやはり私の記憶化検索の精髄で、もう少しで意味が出るところだったが、後で重点的に表記して、肝心なところはdfs関数の部分を見なければならない.

#include
#include 
using namespace std;

int r,c;
int a[1000][1000];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};//           

int f[1000][1000];
int cnt=0;
//         
//        ？                   ，         ，       

int dfs(int x,int y){
	if(f[x][y]) return f[x][y];//                       ，           
	for(int i=0;i<=3;i++)
	{
		if(a[x][y]>a[x+dx[i]][y+dy[i]]&& x+dx[i]>=1 && x+dx[i]<=r && y+dy[i]>=1&& y+dy[i]<=c)
		{
			dfs(x+dx[i],y+dy[i]);
			f[x][y]=max(f[x][y],f[x+dx[i]][y+dy[i]]+1);
			//         ，         ，          ，           		
		}
	}
	return f[x][y];
}

int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	for(int j=1;j<=c;j++)
	cin>>a[i][j];
	
	for(int i=1;i<=r;i++)
	for(int j=1;j<=c;j++)
	   cnt=max(cnt,dfs(i,j));
	
	cout<<cnt+1;//      1，               1，      f[][]     0，        
	
	return 0;
}