SRM647D1Med CtuRobots
問題文が難しい．
問題概要(原文)
$B$ 円持っている， $N$ 台のロボットがいて，$i$ 番のロボットの値段は $Cost_i$ で燃料タンクは $Cap_i$ の容量を持つ．幾つかのロボットを買って出来る限り遠くまで移動するロボットを作りたい．ルールは以下のとおり．
- 全てを同時に出発させる
- 各ロボットは好きなタイミングで次のロボットに燃料を渡せる．
- 各ロボットは最終的に原点に戻ってきたい
考察
容量が安いやつから順番に並べた方が良さそうことが直感的に分かる．なので，容量でソートする． 燃料は次のやつにしか渡せない．どれだけ遠くにいけるようになるかというと，$X$ まで行けるときに，$Cap_i+X/3$ だけ遠くに行けるようになる． ここまでわかると後は単純なナップサックDP(最後のやつは戻ってこないといけないので $2$ で割ってやる)．計算量は $O(BN)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CtuRobots
{
public double maxDist(int B, int[] cost, int[] cap)
{
Array.Sort(cap, cost);
var dp = new double[B + 1];
for (int i = 0; i < B + 1; i++)
dp[i] = -1000000000;
dp[0] = 0;
for (int i = 0; i < cost.Length; i++)
{
var x = cost[i];
double C = cap[i];
for (int j = B - x; j >= 0; j--)
{
if (dp[j] < -1) continue;
dp[j + x] = Math.Max(dp[j + x], C + dp[j] / 3);
}
}
return dp.Max() / 2;
}
}
コメント
- よくわからないときは定式化が大事
- 丁寧に考察すれば実装は非常に単純．
