はまやんはまやんはまやん

hamayanhamayan's blog

EllysSki [2019 Topcoder Open Algo 1B Easy]

N個の山がある。
高さは順にH[i]である。
ある山からスタートして、左か右かにスキーで降りていく。
高さが同じか低いなら降りられる。
途中で方向は変えられないとき、一回の滑降で最高何個の山を通れるか。

1≦N≦50
1≦高さ≦1000

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

解説

全探索する。
自分は+1していくのと、-1していくので、左右への移動をシミュレートした。

struct EllysSki {
	int getMax(vector <int> height) {
		int n = height.size();

		int ans = 1;
		rep(st, 0, n) {
			rep(d, -1, 2) if (d != 0) {
				int tot = 0;
				int cu = st;
				int pre = height[cu];
				while (0 <= cu and cu < n and height[cu] <= pre) {
					tot++;
					pre = height[cu];
					cu += d;
					
				}
				chmax(ans, tot);
			}
		}

		return ans;
	}
};