結果

問題 No.409 ダイエット
コンテスト
ユーザー kei
提出日時 2018-02-04 12:26:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 4,774 bytes
コンパイル時間 1,933 ms
コンパイル使用メモリ 175,052 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-06-26 10:28:26
合計ジャッジ時間 6,406 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e16;

/*
 <url:https://yukicoder.me/problems/no/409>
 問題文============================================================
 btkさんは毎日ドーナツを食べています．
 ある日，btkさんは N 日間ダイエットをすることを決意しました．
 btkさんは毎日違うお店でドーナツを買っていて，
 ダイエット開始から i 日目に訪れるお店でドーナツを食べるとDikg体重が増えることが分かっています．
 また，1 日ドーナツを食べるのをやめると，Akg痩せることができます.
 
 しかし，ドーナツを食べない日が続くとストレスが溜まります．
 ここで，ストレス値というパラメータを定義します． ダイエット開始時点でのストレス値は0です．
 1 日ドーナツを食べないとストレス値が 1 溜まり，
 1日の終了時にbtkさんの体重はB∗(ストレス値)B∗(ストレス値)kg増加します．
 ドーナツを食べるとストレス値は 0 に戻ります．
 
 各日において，ストレス値の変化後に体重が変化することに注意してください．
 
 ダイエット開始前のbtkさんの体重を W kgとしたとき，N 日間で何kgに痩せることができるでしょうか．

 =================================================================
 
 解説=============================================================
 
 Convex hull trick
 
 ストレスがj-1溜まっている時 : -A + B * j kg増える
 i日目にドーナツを食べた時 : Di kg増える
 
 考察1 **********************************************
 
 dp[i][j] := i日目でストレスがj溜まっている時の体重の最小
 
 初期条件 dp[0][0] = W, dp[0][1...N] = INF
 
 漸化式
 dp[i][0] = min(dp[i-1][j] + Di)   0 <= j <= N
 dp[i][j] = dp[i-1][j-1] - A + B*j
 
 => ans := min(dp[N][j])  0 <= j <= N
 
 O(N^2)
 
 ***************************************************
 
 考察2 **********************************************
 
 別の考え方　＝＞　最後にドーナツを食べた日のみに注目　（その間の増分は t日間食べていなければ -t*A + t*(t+1)/2 * B とO(1)で計算できる)
 
 dp[i] := i日目にドーナツを食べた時の最小値
 
 初期条件 dp[0] = W
 
 漸化式
 dp[i] = min(Di + dp[j] - (i - j - 1)*A + (i - j - 1)(i - j)/2 * B)   0 <= j <= i-1
 
 iに着目した時（iを定数とみなせれる時)
 
 dp[i] = Di -(i - 1)*A + (i^2 - i)/2*B + min(-jB*i + dp[j] + j*A + (j^2 + j)/2 * B)  0 <= j <= i-1
 
 min内部に関して
 aj = jB
 bj = dp[j] + j*A + (j^2 + j)/2 * B
 Ci := Di - (i-1)*A + (i^2 - i)/2*B
 とすると
 dp[i] = Ci + min(-aj * i + bj)  0 >= j <= i - 1
 
 
 y=−ax+b の形をした k−1 本の直線のうち
 x=k の時 y が最小となるものを選べばよいことになり
 Convex hull trick でもとまる
 
 ================================================================
 */

struct CHT{
    typedef pair<ll,ll> PT;
    typedef ll RT;
    vector<PT> deq; // first * x + second
    int s,t;
    CHT(int n):s(0),t(0){ deq.resize(n); }
    void add(RT a,RT b){  // a: 単調減少
        const PT p(a,b);
        while(s+1 < t && check(deq[t-2],deq[t-1],p)) t--;
        deq[t++] = p;
    }
    RT incl_query(RT x){  // x: 単調増加
        while(s+1 < t && f(deq[s],x) >= f(deq[s+1],x)) s++;
        return f(deq[s],x);
    }
    RT query(RT x){   // 条件なし
        RT low = s-1, high = t-1;
        while(low+1<high) {
            RT mid = (low+high)>>1;
            if (isright(deq[mid], deq[mid+1], x)) low = mid;
            else high = mid;
        }
        return f(deq[high], x);
    }
    
private:
    bool isright(const PT &p1,const PT &p2,RT x){
        return (p1.second-p2.second) >= x * (p2.first-p1.first);
    }
    bool check(const PT &p1,const PT &p2,const PT &p3){
        return (p2.first-p1.first)*(p3.second-p2.second) >= (p2.second-p1.second)*(p3.first-p2.first);
    }
    RT f(const PT &p,RT x){
        return p.first*x + p.second;
    }
};

ll N,A,B,W;
vector<ll> D;
vector<ll> dp;

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> A >> B >> W;
    D.resize(N);
    for(auto &in:D) cin >> in;

    dp.resize(N+1,0);
    dp[0] = W;
    CHT cht((int)N);
    
    for(ll i = 0; i< N;i++){
        cht.add(-B*i,dp[i] + B*(i*i-i)/2 + A*i);
        dp[i+1] = B*(i*i + i)/2 + D[i] - A*i + cht.query(i);
    }
    ll ans = LINF;
    for(ll i = 0; i <= N;i++){
        ans = min(ans , dp[i] - A*(N-i)+ B*(N-i)*(N-i+1)/2);
    }
    cout << ans << endl;
    return 0;
}
0