SRM610 Div1 Medium "AlbertoTheAviator"
問題
TopCoder Statistics - Problem Statement
訳
アルバートは航空の第一人者だ。彼は"14-bis"と呼ばれる航空機のパイロットでもある。初めに、この航空機の燃料タンクにはFだけ燃料が入っている。
アルバートにはフライトミッションをいくつか抱えていた。それらのミッションは全て発着場所は同じであり、好きな順番で開始することができる。しかし、各ミッションは多くても一度までしかできない。あなたは2つのint[] duration, refuelが与えられる。
duration[i]は、ミッションiを完了させるために必要な燃料であり、ミッションiを行うと燃料はduration[i]だけ減る。それから彼はrefuel[i]だけ燃料を買い、増やすことができる。また、duration[i] > refuel[i]が常に成り立つ。
アルバートは今ある燃料で足りているミッションのみ選ぶことができる。つまり、ミッションiを行うには、燃料タンクがduration[i]以上でなくてはならない。
アルバートがこなすことができるミッションの数の最大値を返せ。
制約
1 <= F <= 5000
1 <= ミッションの数 <= 50
1 <= duration[i] <= 5000
0 <= refuel[i] < duration[i]
解法
SRM 610 Medium - Hiro180の日記 - TopCoder部がとても参考になりました。
問題の条件で50個あるミッションのうち、好きなものを選ぶことができるとある。これを素直に守っていると50!もの方法があって、とても計算量を落とせそうにない。
ここは、よくあるナップサック問題に帰着できないか考えるのが正解だったみたい。
ソースコード
class AlbertoTheAviator { public: int MaximumFlights(int F, vector <int> D, vector <int> R) { int N = D.size(); // Rが大きい順で、次いでDが大きい順 for (int i = 0; i < N; i++) { for (int j = 0; j + 1 < N; j++) { if (R[j] < R[j + 1] || (R[j] == R[j + 1] && D[j] < D[j + 1])) { swap(D[j], D[j + 1]); swap(R[j], R[j + 1]); } } } int dp[55][55]; memset(dp, -1, sizeof(dp)); dp[0][0] = F; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (D[i] <= dp[i][j]) { // 使う dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] - D[i] + R[i]); } // 使わない dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); } } for (int i = N; i >= 0; i--) { if (dp[N][i] != -1) return i; } return -1; } };