观察之后可以发现，每次蓄力之后释放，等价于蓄力到最后一次性释放。每次蓄力water和fire增长的值的固定的，设最后蓄力cnt次，那么最终water = w * cnt，fire = f * cnt，如果要让蓄力次数尽可能少，容易想到要让water和fire尽可能消耗光。water和fire的比例是固定的，所以我们只要把s中的所有元素分为两组，两组的元素和的比例尽量接近于water和fire的比例即可。
这转换为了一个子集合问题。我们先预处理得到minv1和minv2，表示蓄力最少次数时water和fire的值是多少。然后寻找答案。
因为n <= 100, s[i] <= 1e4，所以minv1, minv2 <= 1e6，我们利用动态规划来解决这个问题。dp[i] [j] = true/false，表示在前i个数里是否能取得和为j的组合，i <= n, j <= maxv，maxv = O(n * 1e4)。所以时间复杂度和空间复杂度都是O(n^2 * 1e4)。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll find_minv(vector<int> & s, ll minv){ 6 int n = s.size(); 7 const int maxv = (n + 1) * 1e4 + 10; 8 vector< vector<bool>> dp(n + 10, vector<bool>(maxv, false)); 9 for(int i = 0; i <= n; i++){ 10 dp[i][0] = true; 11 } 12 13 for(int i = 1; i < n; i++){ 14 for(int j = 0; j < maxv; j++){ 15 if(dp[i - 1][j]){ 16 dp[i][j] = true; 17 if(j + s[i] < maxv){ 18 dp[i][j + s[i]] = true; 19 } 20 } 21 } 22 } 23 24 for(int j = 0; j < maxv; j++){ 25 if(dp[n - 1][j] && j >= minv){ 26 return j; 27 } 28 } 29 return 1; 30 } 31 32 void solve(){ 33 ll w, f; 34 cin >> w >> f; 35 ll n; 36 cin >> n; 37 vector<int> s(n + 1); 38 s[0] = 0; 39 for(ll i = 1; i <= n; i++){ 40 cin >> s[i]; 41 } 42 43 ll sum = 0; 44 for(ll i = 1; i <= n; i++){ 45 sum += s[i]; 46 } 47 ll minv1 = (sum * w + f + w - 1) / (f + w); 48 ll minv2 = (sum * f + f + w - 1) / (f + w); 49 ll ans1 = (find_minv(s, minv1) + w - 1) / w; 50 ll ans2 = (find_minv(s, minv2) + f - 1) / f; 51 ll ans = min(ans1, ans2); 52 cout << ans << endl; 53 } 54 55 int main(){ 56 int t = 1; 57 cin >> t; 58 while(t--){ 59 solve(); 60 } 61 }