SRM 492 div1 easy:TimeTravellingGardener
昔の easy は簡単(最初に考えた方針が間違えていて, しかもサンプルが無かったら絶対 WA してた)。
解法
n = (木の本数) とします。
まず, 答えが n-1 以下になることは明らかです。一番低い木に合わせて他の木を削れば良いので。
答えを n-2 以下にしたいとしましょう。その際, そのままの高さで残しておく可能性のある木の組 (i, j) を選べば, 直線が一意に定まります。なので後はこの直線に対して木の高さを調整すれば OK です。
ただ, 木の高さとしてありえないものがあった時は, その場合の (i, j) の組は採用できないので無視です。
class TimeTravellingGardener { public: int determineUsage(vector <int> d, vector <int> h) { int n = h.size(); int ret = n-1; vector<int> D(n); for (int i = 1; i < n; i++) D[i] = D[i-1]+d[i-1]; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int cnt = 0; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; int H = h[i]*(D[j]-D[i]) + (h[j]-h[i])*(D[k]-D[i]); if (h[k]*(D[j]-D[i]) < H || H < 0) { cnt = n; break; } else if (h[k]*(D[j]-D[i]) != H) cnt++; } ret = min(ret, cnt); } } return ret; } };