算法
(01背包) $O(n\sum t_i/w)$
题意是让我们最小化两个烤箱所用时间的最大时间,显然是 $01$ 布尔背包问题。
朴素做法是 $dp[i][j]$ 表示前 $i$ 个时间能否选出若干个拼出时间 $j$,转移方程为 $dp[i + 1][j + t_i] \Big|= dp[i][j]$
考虑可以滚动掉第一维,然后考察转移,实质上是将原数组的01串左移了 $t_i$ 位与原串取或。
于是如果令 $dp$ 为一个 bitset
的话,则转移方程可以写成 $dp \Big|= dp * 2^{t_i}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::bitset;
int main() {
int n;
cin >> n;
bitset<100001> dp;
dp[0] = 1;
int tot = 0;
rep(i, n) {
int t;
cin >> t;
tot += t;
dp |= dp << t;
}
int ans = tot;
rep(i, tot + 1) if (dp[i]) ans = min(ans, max(i, tot - i));
cout << ans << '\n';
return 0;
}