F. Magic Will Save the World

kurish / 2023-08-28 / 原文

F. Magic Will Save the World

观察之后可以发现，每次蓄力之后释放，等价于蓄力到最后一次性释放。每次蓄力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)。

最后打完dp的表格之后查询取前n个数时>=minv的最小值是多少，如果不存在，则说明所有数之和比minv小，蓄力一次就足够了。

 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 }