第七回 アルゴリズム実技検定 O - コンピュータ
公式解説とか正解コードとかブログとかいっぱい見た
dp[i]= i日目に必要なコンピュータを手に入れるまでに必要な最小の金額
というdpテーブルを作ることを考える
dp[0] = 0にしておく
dp[i] = min(dp[j]+B[i] | B[i] <= ( Σ(0~j)A[k] - dp[j]) )
後ろを全部調べるとO(n^2)になるので、
B[i] <= ( Σ(0~j)A[k] - dp[j]) ←この条件を満たす遷移をmin-outヒープで、
dp[j] ←上のヒープに入っている遷移の中で最小をc++のmultisetで出す
dp[X]を計算した後
ヒープに、 ( Σ(0~X)A[k] - dp[X], dp[X] )
multisetに、(dp[X] , Σ(0~X)A[k] - dp[X] )
と、(a, b) (b, a)みたいなタプルを入れる
dp[X+1]を計算する時、
ヒープ中のタプルで,これを(a, b)としたときに、a<B[X+1]なものを取り除き、multisetから(b, a)を取り除く。
dp[X+1] = B[X+1] + (multiset中最小の要素の第一成分)
と更新できる。
むずい
fn solve(){
let sssss = std::io::stdin();
let mut sc = Scanner { stdin: sssss.lock() };
let mut N:usize =sc.read();
let mut A = vec![0i64;N+1];
let mut B = vec![0i64;N];
for i in 0..N{
A[i+1] = sc.read();
B[i] = sc.read();
A[i+1]+=A[i];
}
let mut h = BinaryHeap::new();
let mut m = MultiSet::new();
let mut ma = -1;
h.push*1;
m.insert*2;
let mut dp = vec![0;N+2];
for i in 0..N{
if B[i]<=ma{
B[i] = ma;
}
else{
ma = B[i];
}
while(h.len() != 0){
let mut t = h.pop().unwrap();
if -(t.0)<B[i]{
m.remove(&(t.1, -t.0));
}
else{
h.push(t);
break;
}
}
if m.set.len() == 0{
println!("-1");
return;
}
let mut mm = m.get_min().unwrap();
dp[i+1] = B[i]+mm.0;
if i != N-1{
h.push*3;
m.insert*4;
}
}
println!("{}", A[N]-dp[N]);
}
