mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #213 (Div. 1) B. Free Market

解法

集合 A から, D 円以内で交換できる品の集合 B があるなら, 集合 A から集合 B にシフトしていく, というのを貪欲にやっていけば良いです。

集合 A と集合 B に同じ品の集合 C がある可能性がありますが, その場合は, A\C, B\C を交換するだけで D 円増やすことが出来るということなので, 問題ありません。

コードとしては, まず dp で「集合として値段の合計がいくらになるものがあり得るか」というのを考えて, その後 D 円以下でなるべく増えるように各施工で値段の合計を増やしていきます。

const int MAXN = 55;
int C[MAXN];
bool ok[MAXN*10000];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; i++) cin >> C[i];
    ok[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = MAXN*10000-1; j >= 0; j--) {
            if (ok[j]) ok[j+C[i]] = true;
        }
    }
    int cur = 0;
    for (int cnt = 0; ; cnt++) {
        bool ng = true;
        for (int i = cur+d; i > cur; i--) {
            if (ok[i]) {
                ng = false;
                cur = i;
                break;
            }
        }
        if (ng) {
            cout << cur << " " << cnt << endl;
            break;
        }
    }
    return 0;
}