結果

問題 No.409 ダイエット
ユーザー keikei
提出日時 2018-02-04 12:26:19
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 3 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 3 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 3 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 3 ms
5,376 KB
testcase_46 AC 2 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 3 ms
5,376 KB
testcase_49 AC 2 ms
5,376 KB
testcase_50 AC 2 ms
5,376 KB
testcase_51 AC 2 ms
5,376 KB
testcase_52 AC 2 ms
5,376 KB
testcase_53 AC 3 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
testcase_55 AC 30 ms
7,680 KB
testcase_56 AC 26 ms
12,036 KB
testcase_57 AC 60 ms
12,160 KB
testcase_58 AC 25 ms
7,168 KB
testcase_59 AC 36 ms
8,804 KB
testcase_60 AC 23 ms
6,656 KB
testcase_61 AC 52 ms
11,264 KB
testcase_62 AC 57 ms
11,724 KB
testcase_63 AC 53 ms
11,136 KB
testcase_64 AC 29 ms
7,296 KB
testcase_65 AC 54 ms
11,460 KB
testcase_66 AC 59 ms
12,092 KB
testcase_67 AC 44 ms
9,984 KB
testcase_68 AC 36 ms
8,704 KB
testcase_69 AC 50 ms
10,992 KB
testcase_70 AC 56 ms
10,496 KB
testcase_71 AC 29 ms
7,296 KB
testcase_72 AC 67 ms
12,092 KB
testcase_73 AC 62 ms
11,384 KB
testcase_74 AC 38 ms
8,320 KB
testcase_75 AC 62 ms
11,392 KB
testcase_76 AC 43 ms
8,960 KB
testcase_77 AC 30 ms
7,168 KB
testcase_78 AC 35 ms
7,808 KB
testcase_79 AC 27 ms
6,784 KB
testcase_80 AC 61 ms
11,648 KB
testcase_81 AC 59 ms
11,344 KB
testcase_82 AC 45 ms
9,216 KB
testcase_83 AC 47 ms
9,728 KB
testcase_84 AC 39 ms
8,576 KB
testcase_85 AC 6 ms
5,376 KB
testcase_86 AC 37 ms
8,440 KB
testcase_87 AC 54 ms
10,496 KB
testcase_88 AC 22 ms
6,016 KB
testcase_89 AC 44 ms
9,344 KB
testcase_90 AC 20 ms
6,016 KB
testcase_91 AC 47 ms
9,600 KB
権限があれば一括ダウンロードができます

ソースコード

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