题解 [ABC204D] Cooking

[ABC204D] Cooking

动态规划题目应当从转移可行性入手，我们考虑这道题目，由于物品没有顺序，又不适用状态压缩 DP，所以只有考虑贪心或者其他转移方式的 DP。

我们发现 \sum T_i 十分小，且一个物品先烧后烧并不会对贡献产生影响。于是便想到了 F_{k, i, j} 表示只考虑前 k 个物品，左炉烧 i 分钟，右炉烧 j 分钟是否可能。

发现不行，这时候我们考虑 DP 换键，我们把状态设计为 F_{i, j} 为左炉烧制 j 分钟，右炉最少烧制多少分钟。

这样期望得分 100 pts，但是我们还可以更优。

第一维可以进行滚动，最终空间复杂度降低到 O(\sum T_i)，时间复杂度 O(n \times \sum T_i)。

The code

#include <bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

const int N = 1e5 + 10;

int ast, bst, n, a[N], F[2][N];

int main() {
    cin >> n;
    L(i, 1, n) cin >> a[i];
    memset(F, 0x3f, sizeof(F));
    F[0][0] = 0;
    L(i, 1, n) {
      L(j, 0, N-1)
        if(j >= a[i]) F[i % 2][j] = min(F[(i-1) % 2][j]+a[i], F[(i-1) % 2][j-a[i]]);
        else F[i % 2][j] = F[(i-1) % 2][j]+a[i];
    }
    int Ans = N*100;
    L(i, 0, N-1)
      Ans = min(Ans, max(F[n % 2][i], i));
    cout << Ans << '\n';
    return 0;
}

如果 n \le 10^4 保证 \sum T_i \le 10^6 怎么做？

我们发现其实我们只需要求出左炉的所有组合可以凑出来的数字即可，F_{i} 表示 i 这个数字能否被凑出。

如果直接暴力转移，同样会超时，这时候我们需要进行一下 Bitset 优化。

时间复杂度 O(n \times \frac{\sum T_i}{w})，其中 w 通常为 32（计算机的位数），而且数据常常造不满，这个时间复杂度跑 2\text{s}，应当问题不大。

The code

#include <bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

const int N = 1e5 + 10;

bitset<N> S; int n, x, s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    S[0] = 1;
    cin >> n;
    L(i, 1, n) cin >> x, S = S | (S << x), s += x;
    int ans = 1e9;
    L(i, 0, s/2)
      if(S[i]) ans = min(ans, max(i, s-i));
    cout << ans << '\n';
    return 0;
}