はまやんはまやんはまやん

hamayanhamayan's blog

Cut onion [Kotamanegi Online Judge No.66]

https://kotamanegi.com/Problems/view/?page=66

解法

https://kotamanegi.com/Submission/view/index.php?SubmissionID=2149

間接的に問題を解く。
まずは、以下のbitDPをする。

dp[gr][msk] := gr個のグループにmsk集合の友達に必要なこたまねぎを分けたときに必要なこたまねぎの最小数
このDPの意味がわかりにくいと思うが、公式解説も参照してみて欲しい。
このDPの更新のために
f[msk] := msk集合の友達に必要なこたまねぎを分けるときに必要となるこたまねぎの数
を作っておこう。
これはceil((msk集合に含まれる友達が求めるこたまねぎの総和)/B)である。
配列fとO(3^N)の部分集合の列挙テクを用いればbitDP更新はできる。
 
答えをここから導こう。
dp[gr][(1 ≪ N)-1]≦Kであれば、gr個のグループに分けることができることになる。
gr個のグループに分けることができれば、分割数はN-gr回で済む。
よって、dp[gr][( 1 ≪ N ) - 1 ] ≦Kである最大のgrを求めて、N-grが答え。

int N, K, B, A[16];
int dp[20][1 << 16], f[1<<16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> B;
    rep(i, 0, N) cin >> A[i];

    rep(gr, 0, N + 1) rep(msk, 0, 1 << N) dp[gr][msk] = inf;
    dp[0][0] = 0;

    rep(msk, 0, 1 << N) {
        int sm = 0;
        rep(i, 0, N) if (msk & (1 << i)) sm += A[i];
        f[msk] = (sm + B - 1) / B;
    }

    rep(gr, 1, N + 1) rep(msk, 0, 1 << N) {
        for (int msk2 = msk; msk2 >= 0; msk2--) {
            msk2 &= msk;
            if(msk2 != msk) chmin(dp[gr][msk], dp[gr - 1][msk2] + f[msk - msk2]);
        }
    }

    int ma = -1;
    rep(gr, 1, N + 1) if (dp[gr][(1 << N) - 1] <= K) chmax(ma, gr);

    int ans = N - ma;
    cout << ans << endl;
}