一見 な bitDP だけど、これはアレだ!!!
よくある にできるやつだ!!!!!
問題概要
個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。
制約
解法
とりあえず一見 な bitDP に見える。AGC 026 F - Manju Game の最後の DP でやるような工夫と同様の工夫をちょっとやると
dp[S][k] := S の中のいくつかについては k 個の値 T 以下のグループに分類して、残ったやつの総和として取りうる最小値 (全部を k 個の値 T 以下のグループに分けられるなら 0)
とすると計算量を落とせる。
#include <iostream> #include <vector> using namespace std; const int INF = 1<<29; int N, T; vector<int> t; vector<vector<int> > dp; int main() { cin >> T >> N; t.resize(N); for (int i = 0; i < N; ++i) cin >> t[i]; dp.assign(N+1, vector<int>((1<<N)+1, INF)); dp[0][0] = 0; for (int k = 0; k < N; ++k) { for (int bit = 0; bit < (1<<N); ++bit) { if (dp[k][bit] <= T) dp[k+1][bit] = 0; for (int i = 0; i < N; ++i) { if (bit & (1<<i)) continue; int nbit = bit | (1<<i); dp[k][nbit] = min(dp[k][nbit], dp[k][bit] + t[i]); if (dp[k][nbit] + t[i] <= T) dp[k+1][nbit] = 0; } } } int res = N; for (int k = 0; k < N; ++k) if (dp[k][(1<<N)-1] == 0) res = min(res, k); cout << res << endl; }