simezi_tan https://blog.hatena.ne.jp/simezi_tan/ simezi_tanの日記 https://simezi-tan.hatenadiary.org/ AOJ ICPC 動的計画法 問題 空から風船が落ちてくるので、それを台車で回収したい。 それぞれの風船は、時間t[i]にx座標x[i]の地点に落ちる。 このとき台車はちょうどx[i]の位置にいる必要がある。 台車は回収した風船を、x座標が0の地点の小屋に入れることができる。 台車には風船が3つまで乗り、風船がk個乗っているときに単位距離を移動するのにかかる時間はk+1である。 台車は時刻0のとき小屋にいる。 台車は風船を全て回収できるか、できるならそのときの移動距離の最小値を、 そうでないなら最初に回収できなくなる風船の番号を答えよ。 制約条件 n≦40 x[i]≦100 t[i]≦50000 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsimezi-tan.hatenadiary.org%2Fentry%2F20110926%2F1316993557" title="AOJ 1306 ICPC Asia resional 2010 Problem B: Balloon Collecting - simezi_tanの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-09-26 08:32:37 rich https://simezi-tan.hatenadiary.org/entry/20110926/1316993557 1.0 100%