No.409 ダイエット yukicoder
問題概略
N日あり、毎日ドーナッツiを食べるか食べないかを選択できる。
iを食べるとDi体重が増えるがストレスが0に、食べないと、体重がA減る代わりにストレスが1増え、体重がB*(ストレス)増える。
初期体重はW、最終日の最軽は何か
1≤N≤3∗105
0≤A,B,W≤106
0≤Di≤106
解法
satanicさんの解説を参考にしました(式が少し違うので注意)
yukicoder No.409 ダイエット - sataniC++
ドーナッツを食べるとストレスが0になるので、最後にドーナッツを食べた日でdpを遷移したら良さそう
dp[i] := i日目にドーナッツを食べた時の体重の最小変化量
dp[0] = 0DP[i]====0min0≤t≤i−1(DP[t]−A(i−t−1)+(i−t−1)(i−t)2B+D[i])min0≤t≤i−1(DP[t]+tA+−2it+t2+t2B)−A(i−1)+i2−i2B+D[i]min0≤t≤i−1(DP[t]+tA+t2+t2B−itB)−A(i−1)+i2−i2B+D[i]として
最後にドーナッツを食べた日tで、 //iは1からなので
dp[i] = min(dp[t] + A(i-t-1) + (i-t-1)(i-t)/2*B+d[i-1])となる
= min(dp[t] + tA + (t^2+t)/2*B - itB) - A(i-1) + (i^2 -i)/2 *B +d[i-1]
minの外側はiに対する定数であり、minの内側は(-tB)i+(dp[t]+tA+(t^2+t)/2*B)となりiに対する1次式になるのでconvex hull trick が使える。
具体的なコードは
long[] dp = new long[N + 1];
dp[0] = 0;
c.add(0, 0);
for (int i = 1; i < N + 1; i++) {
dp[i] = c.min(i) - A * (i - 1) + i * (i - 1L) / 2 * B + D[i - 1];
c.add(-i * B, dp[i] + i * A + i * (i + 1L) / 2 * B);
}
cはconvex hull trick
一日も食べない場合は(-tB)i = 0かつ(t^2+t)/2*B - itB) = 0となるので、まず直線 0x + 0を入れておく。
求めたいdpの添字に対応した直線であり、dp[i]を求めたいのでc.min()にiを渡す。iが1からなのでDにはi-1を渡す。
今求めたdp[i]を使った直線を入れる必要があるので、そのiに基づいた式（(-tB)i+ (dp[t]+tA+(t^2+t)/2*B)）を代入しておく
最終的にmin( W + dp[i] + (iの次の日から断食した場合の痩せたり太ったりする量))が答え
https://yukicoder.me/submissions/291088
>|java|
public static void solve() throws Exception {
//longを忘れるなオーバーフローするぞ
int N = ni();
long A = ni();
long B = ni();
long W = ni();
long[] D = nla(N);
//i日目に食べた時の最小
ConvexHullTrick c = new ConvexHullTrick(N + 100, true, false, true);
long[] dp = new long[N + 1];
dp[0] = 0;
c.add(0, 0);
for (int i = 1; i < N + 1; i++) {
dp[i] = c.min(i) - A * (i - 1) + i * (i - 1L) / 2 * B + D[i - 1];
c.add(-i * B, dp[i] + i * A + i * (i + 1L) / 2 * B);
}
long res = Long.MAX_VALUE;
for (int i = 0; i < N + 1; i++) {
res = min(res, (W + dp[i] - (N - i) * A + (long) (N - i) * (N - i + 1) / 2 * B));
}
System.out.println(res);
}
static class ConvexHullTrick {
long[][] line;
int tail;
boolean xinc, minQuery, redBlue;
// add における a が単調非増加、query における x が単調非減少である場合
// add O(n), query O(n + q)
ConvexHullTrick(int n, boolean minQuery, boolean angInc, boolean xinc) {
line = new long[n][2];
tail = 0;
this.minQuery = minQuery;
redBlue = minQuery ^ angInc;
this.xinc = xinc;
}
// ax+b を追加。a は単調非増加とする
private void add(long a, long b) {
line[tail][0] = a;
line[tail][1] = b;
tail++;
while (tail >= 3) {
if (check(line[tail - 3], line[tail - 2], line[tail - 1])) {
break;
}
line[tail - 2][0] = line[tail - 1][0];
line[tail - 2][1] = line[tail - 1][1];
tail--;
}
}
// i 番目の直線を使った時の f(x) の値
private long f(int i, long x) {
return line[i][0] * x + line[i][1];
}
// curr の直線が必要な場合 true
private boolean check(long[] prev, long[] curr, long[] next) {
if (redBlue) return (next[1] - curr[1]) * (curr[0] - prev[0]) < (curr[1] - prev[1]) * (next[0] - curr[0]);
else return (next[1] - curr[1]) * (curr[0] - prev[0]) > (curr[1] - prev[1]) * (next[0] - curr[0]);
}
int head = 0;
long min(long x) {
if (!minQuery) System.out.println(1 / 0);
if (xinc) {
while (tail - head >= 2 && f(head, x) >= f(head + 1, x)) {
head++;
}
return f(head, x);
} else {
int min = -1;
int max = tail - 1;
while (max - min > 1) {
int med = (max + min) / 2;
if (f(med, x) >= f(med + 1, x)) {
min = med;
} else {
max = med;
}
}
return f(max, x);
}
}
long max(long x) {
if (minQuery) System.out.println(1 / 0);
if (xinc) {
while (tail - head >= 2 && f(head, x) <= f(head + 1, x)) {
head++;
}
return f(head, x);
} else {
int min = -1;
int max = tail - 1;
while (max - min > 1) {
int med = (max + min) / 2;
if (f(med, x) <= f(med + 1, x)) {
min = med;
} else {
max = med;
}
}
return f(max, x);
}
}
}
||
DP[i]
====0min0≤t≤i−1(DP[t]−A(i−t−1)+(i−t−1)(i−t)2B+D[i])min0≤t≤i−1(DP[t]+tA+−2it+t2+t2B)−A(i−1)+i2−i2B+D[i]min0≤t≤i−1(DP[t]+tA+t2+t2B−itB)−A(i−1)+i2−i2B+D[i]
DP[i]====0min0≤t≤i−1(DP[t]−A(i−t−1)+(i−t−1)(i−t)2B+D[i])min0≤t≤i−1(DP[t]+tA+−2it+t2+t2B)−A(i−1)+i2−i2B+D[i]min0≤t≤i−1(DP[t]+tA+t2+t2B−itB)−A(i−1)+i2−i2B+D[i]DP[i]====0min0≤t≤i−1(DP[t]−A(i−t−1)+(i−t−1)(i−t)2B+D[i])min0≤t≤i−1(DP[t]+tA+−2it+t2+t2B)−A(i−1)+i2−i2B+D[i]min0≤t≤i−1(DP[t]+tA+t2+t2B−itB)−A(i−1)+i2−i2B+D[i]
