yukicoder No.393 2本の竹
解法
想定解とはちょっと違う解法になりました。
考察で, 「長さの短い竹をなるべく受け付ける方が良い」というのは変わりません。
なので, 配列 A をソートしておけば, 選ばれる竹は, [0, upper) というような区間を選ぶことになるはずです。この選び方が可能であるかを判定したいのですが,
dp[i] = (N1 の竹を使って合計長さが i であるような注文を受け付けることは可能か) という dp をします。すると, sum = A[0]+...+A[upper-1] として, N2 が担当しなければならない注文合計長さは sum-i になりますが, これが OK かどうかは, N2 >= sum-i が成り立つかどうかで判定できます。
結局計算量は O(N1 * m^2) です。
const int MAX = 100100; bool dp[MAX]; // [0, upper) のものをすべて提供しても大丈夫か bool isOK(int N1, int N2, const vi& A, int upper) { if (upper == 0) return true; int sum = 0; for (int i = 0; i < upper; i++) sum += A[i]; if (sum > N1+N2) return false; memset(dp, false, sizeof(dp)); dp[0] = true; for (int i = 0; i < upper; i++) { for (int j = MAX-1; j >= 0; j--) { if (dp[j]) { if (j+A[i] <= N1) dp[j+A[i]] = true; } } } for (int i = MAX-1; i >= 0; i--) { if (dp[i] && sum-i <= N2) return true; } return false; } void solve() { int N1, N2; cin >> N1 >> N2; if (N1 > N2) swap(N1, N2); int m; cin >> m; vector<int> A(m); for (int i = 0; i < m; i++) cin >> A[i]; sort(A.begin(), A.end()); for (int i = m; i >= 0; i--) { if (isOK(N1, N2, A, i)) { cout << i << endl; return; } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; while (T--) { solve(); } return 0; }