2/7 PKU

Algorithm PKU

2433 Landscaping

ある地面の地形が与えられる。今、地面の極大部分の数が高々K個になるように、地面を削りとりたい。削りとるべき最小の土の量を求めよ。

up[i][j][k] : i番目まで見ていて、現在の高さj、山の右端はk回出てきて、絶賛上昇中
dw[i][j][k] : i番目まで見ていて、現在の高さj、山の右端はk回出てきて、絶賛下降中
としてDPしたらぎりぎりで通った

2467 Snow Clearing

いくつかの道があって除雪が必要だが、除雪機が1台しかない。「すべての道の両方向の道を除雪するために」必要な時間を求めよ。

DFSっぽいことをすると、すべての道で両方向の道が除雪され、すべての道は高々1往復しかされないためこれが最善である。