yukicoder No.409 ダイエット
この問題実は btk さんから相談をもらっていたんですけど時間内に解けなかった…(主に蟻本を探していた)
解法
dp[i] = (i 日目に最後にドーナツを食べる際の最小体重)とします。この発想の時点で結構頭良い気がします(こういう風に書くと状態に「何日間ドーナツを食べていないか」というのを持たなくても良いところが good)。
これで普通に状態遷移を考えると,
dp[i] = min(dp[j] - (i-j-1)*A + (i-j)*(i-j-1)/2 * B + D[i])
となり, これをすべての j について調べることになります。これを普通にやると O(n^2) かかるんですが, 上式を変形して
dp[i] = D[i] - (i-1)*A + (i*i-i)/2*B + min(-B*j*i + j*A + (j*j+j)/2*B + dp[j])
というように変換すると, 結局各 j について考えるべきは, min の中身だけになります。さらに, min の中身は i の一次式の形をしているので, 蟻本に書いてある convex-hull trick を用いることで全体として O(n) の時間で各 i の min 値を求めることができます。
const int MAXN = 300300; ll dp[MAXN]; int deq[MAXN]; int N, A, B, W; bool check(int f1, int f2, int f3) { ll a1 = -(ll)B*f1, b1 = (ll)f1*A + ((ll)f1*f1+f1)/2 * B + dp[f1]; ll a2 = -(ll)B*f2, b2 = (ll)f2*A + ((ll)f2*f2+f2)/2 * B + dp[f2]; ll a3 = -(ll)B*f3, b3 = (ll)f3*A + ((ll)f3*f3+f3)/2 * B + dp[f3]; return (a2-a1) * (b3-b2) >= (b2-b1) * (a3-a2); } ll f(int j, int x) { return -(ll)B*j*x + (ll)j*A + ((ll)j*j+j)/2*B + dp[j]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> A >> B >> W; vector<int> D(N); for (int i = 0; i < N; i++) cin >> D[i]; dp[0] = 0; int s = 0, t = 1; deq[0] = 0; for (int i = 1; i <= N; i++) { while (s+1 < t && f(deq[s], i) >= f(deq[s+1], i)) s++; dp[i] = f(deq[s], i) + D[i-1] - (ll)(i-1)*A + ((ll)i*i-i)/2*B; // 末尾から最小値を取る可能性がなくなったものを取り除く while (s+1 < t && check(deq[t-2], deq[t-1], i)) t--; deq[t++] = i; } ll ans = 1ll<<60; for (int i = 0; i <= N; i++) { ll d = N-i; ans = min(ans, dp[i]+B*(d+1)*d/2 - A*d); } cout << ans+W << endl; return 0; }