POJ 1088 滑雪

問題文が中国語⇒英語でさえ読めないのに中国語とかむり。

なんとか推測して頑張りました。

DPの問題解きたいと思って、簡単そうなのを見つけたのがこれだったが、これはDPと言えるのか❓？？

えーと計算量は、O(シラン)ぐらいです（かなり適当なオーダー）

なんか深さ優先探索（？）的なので解いてる人っぽいのを解き終わった後見つけましたが、あんま使いたくないのでつかいませんでした。

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

int main(){

int r,c,ans = 0;;

int t[103][103] = {0};

int dp[103][103] = {0};

priority_queue<int, vector<int> , greater<int> >que;



scanf("%d%d",&r,&c);

for(int i = 1;i <= r;i++){
	for(int j = 1;j <= c;j++){
		scanf("%d",&t[i][j]);
		que.push(t[i][j]);
	}
}


while(!que.empty()){
	int nau = que.top(); que.pop();
	
	for(int i = 1;i <= r;i++){
		for(int j = 1;j <= c;j++){
			if(t[i][j] == nau && dp[i][j] == 0){
			dp[i][j] = 1;
			for(int k = 0;k < 4;k++){
			int x = j + dx[k];
			int y = i + dy[k];
			if(t[y][x] < nau) dp[i][j] = max(dp[i][j],dp[y][x]+1);
			}
			ans = max(ans,dp[i][j]);
			goto out;
			}
		}
	}
	out:
	;
}

printf("%d\n",ans);

return 0;

}