牛客周赛 Round 68 E-博丽神社的巫女（二）

原题链接

https://ac.nowcoder.com/acm/contest/95928/E

题面

解题思路

a[i]进行不断地除以2操作后可以得到log2(a[i])种情况，如果将每个a[i]操作获得的情况各自分组，相当与第i组中有log2(a[i])个数。

数组中操作后所有的元素和等于100000，相当与每组数种都必须选出一个数，使得和恰好为100000。

通过上面分析得到，这实际上是个分组背包问题。

设f[i][j]为在前i组数中是否可以凑出j，f[i][j] = 1表示可以，f[i][j] = 0表示不能。

若从第i组数中选出了x，且f[i - 1][j - x] = 1(即前i - 1组当中可以凑出j - x），则前i组中能凑出j，那么j可以被凑出，。

题目还要求输出一个具体方案，只需要在计算时记录前驱状态即可，具体的说就是如果f[i][j] = 1是通过f[i - 1][j - x] = 1得到的，那么记录下f[i][j]的前驱状态为f[i - 1][j - x]，同时记录下第i组得到数字x的操作次数（a[i]除以2几次得到的x)。最后输出具体方案的时候从末尾状态f[n][m]向前回溯即可。

代码（CPP）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3fLL;
const int m = 1e5;
int f[maxn][maxm];      // f[i][j]代表在前i组数当中每一组选一个，能否让和为j
int pre[maxn][maxm];    // 记录每一组的选择
int Cnt[maxn][maxm];    // 记录操作（除以2）的次数

void solve() {
    int n;
    cin >> n;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        int cnt = 0;
        while (x > 0) {
            for (int j = x; j <= m; j++) {
                if (f[i - 1][j - x]) {
                    f[i][j] = 1;
                    pre[i][j] = j - x;
                    Cnt[i][j] = cnt;
                }
            }
            x /= 2;
            cnt++;
        }
        for (int j = 0; j <= m; j++) {
            if (f[i - 1][j]) {
                f[i][j] = 1;
                pre[i][j] = j;
                Cnt[i][j] = cnt;
            }
        }
    }

    // 输出答案
    if (!f[n][m])
        cout << "-1\n";
    else {
        vector<int> ans;
        int j = m;
        for (int i = n; i >= 1; i--) {
            ans.push_back(Cnt[i][j]);
            j = pre[i][j];
        }
        for (int i = n - 1; i >= 0; i--) {
            if (i != n - 1) cout << " ";
            cout << ans[i];
        }
        cout << endl;
    }
}

int main() {
//     freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}

原文地址：https://blog.csdn.net/qq_45554473/article/details/144808324

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！