[AtCoder] ABC 104 C – All Green
問題
方針
問題を解く順番は関係ないので、コンプリートする問題を全探索します。これは、ビット全探索で解くことはできます。コンプリートした問題の集合を \( 2 \) 進数で表し、点数が \( G \) 未満ならば、コンプリートしていない問題の中で一番点数の高い問題を解き、\( G \) 以上になるかを確かめます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int D, G; cin >> D >> G; int p[D], c[G]; for (int i = 0; i < D; i++) { cin >> p[i] >> c[i]; } int n = 1<<D; int best = INT32_MAX; for (int i = 0; i < n; i++) { int t = 0; int s = 0; for (int j = 0; j < D; j++) { if ((i & (1<<j))) { t += p[j]; s += (j + 1) * 100 * p[j]+ c[j]; } } for (int j = D - 1; j >= 0; j--) { if ((i & (1<<j)) == 0 && s < G) { if ((G - s) / 100 <= p[j] * (j + 1)) { t += max(1, (G - s) / 100 / (j + 1)); s = G; } break; } } if (best > t && s >= G) { best = t; } } cout << best << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません