No.409 ダイエット

No.409 ダイエット - yukicoder
すぐに見えて成長を感じた

解法

断食日数がはっきりしないと面倒なので
dp[i] := i日目に食べる際の最適とする

こうするとdp[j]から遷移する際に断食日数が定まるためやりやすい

これは一見O(n^2)だが、これはconvex hull trickの形をしているのでO(n)やO(n log n)にできる

ところで、このままだとi以前で一回も食べていない場合に遷移できない
そこで1 indexにしてやり、0日目にd[0] = 0を追加してやると上手くいく
また、d[n+1] = 0としてやると、dp [n+1]が求めるべき答え

#320981 No.409 ダイエット - yukicoder

void solve() {
    int a, b, w;
    vi d;
    cin >> n >> a >> b >> w;
    nao(d, n);
    d += 0;
    convexHullDynamic cht(chtMin);
    //i日目に食べる際の答え
    vi dp(n + 2);//1
    rep(i, 1, n + 2) {
        int j = i - 1;
        cht.add(-j * b, dp[j] + (pow(j) + j) * b / 2 + a * j);
        dp[i] = cht.get(i) + (pow(i) - i) * b / 2 - a * i + a + d[i];
    }
    //n+1日目に無を食べる最適が答え
    cout << w + dp[n + 1] << endl;
}