思考了一下以为需要 $O(nC)$ 的算法 然后使用偷瞄答案法发现 $O(nC^2)$ 其实也能水过去 让价值函数w(i)表示耗时 t 就行了

相关概念：泛化物品 定义：考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着你分配给它的费用（体积）变化而变化。

注意到价值和体积其实可以交换的，因为是泛化物品……

如果转移方程是以耗时t为参数，那么容易计算得到 $O(nC^2) = 1200 \times 6000 \times 6000 \approx 4.3 \times 10^{10}$ 而如果是以画的数量为参数，求最小时间，则为 $O(nC^2) = 6000 \times 1000 \times 1000 \approx 8.6 \times 6^9$ 快了 10 倍吧，基本上。 所以最后一个点 TLE 就可以过了（

这里给出两份代码： AC版

#include <iostream>
#include <cstring>

using namespace std;
int s;
struct P1270
{
    int w, pic, left, right;
} nodes[600];
int read(int i)
{
    cin >> nodes[i].w;
    cin >> nodes[i].pic;
    if (nodes[i].pic)
        return i;
    nodes[i].left = i + 1;
    nodes[i].right = read(nodes[i].left) + 1;
    return read(nodes[i].right);
}
int dp[600][1205];
void dfs(int index)
{
    P1270 &n = nodes[index];
    for (int i = 0; i <= n.pic; ++i)
        dp[index][i] = i * 5;
    if (n.pic)
        return;
    // 以 i 为根，前 k 个子树，消耗 j 的时间所偷取最大数量的画
    // f(i, k, j) = max(f(i, k - 1, j - t) + f(v, 2, t - 2w), f(i, k, j))
    // f(i, j) = max(f(i, j - t) + f(v, t - 2w), f(i, j))

    // 以 i 为根，前 k 个子树，偷取 j 张画消耗的最少时间
    // f(i, k, j) = min(f(i, k - 1, j - t) + f(v, 2, t), f(i, k, j))
    // f(i, j) = min(f(i, j - t) + f(v, t), f(i, j))
    auto v = n.left;
    dfs(v);
    auto &left = nodes[v];
    for (int j = 1200; j > 0; --j)
        for (int t = 1; j - t >= 0; ++t)
            dp[index][j] = min(dp[index][j], dp[index][j - t] + dp[v][t] + 2 * left.w);
    v = n.right;
    dfs(v);
    auto &right = nodes[v];
    for (int j = 1200; j > 0; --j)
        for (int t = 1; j - t >= 0; ++t)
            dp[index][j] = min(dp[index][j], dp[index][j - t] + dp[v][t] + 2 * right.w);
}

int main(int, char **)
{
    cin >> s;
    memset(dp, 0x1f, sizeof(dp));
    read(0);
    dfs(0);
    s -= nodes->w * 2 + 1;
    int i = 0;
    for (; dp[0][i] < s; ++i){};
    cout << i - 1;
    return 0;
}

第五个测试点 TLE：

// 前面是相同的

int dp[1000][6005];

void dfs(int index)
{
    P1270 &n = nodes[index];
    for (int i = 1; i <= n.pic; ++i)
        for (int l = 0; l < 5; ++l)
            dp[index][i * 5 + l] = i;
    for (int i = n.pic * 5 + 5; i <= s - 4 * n.w; ++i)
        dp[index][i] = n.pic;
    if (n.pic)
        return;

    auto v = n.left;
    dfs(v);
    auto &left = nodes[v];
    for (int j = s - 2 * n.w - 1; j >= 2 * left.w; --j)
        for (int t = 2 * left.w + 5; j - t >= 0; ++t)
            dp[index][j] = max(dp[index][j], dp[index][j - t] + dp[v][t - 2 * left.w]); // 差异其实是这个
    v = n.right;
    dfs(v);
    auto &right = nodes[v];
    for (int j = s - 2 * n.w - 1; j >= 2 * right.w; --j)
        for (int t = 2 * right.w + 5; j - t >= 0; ++t)
            dp[index][j] = max(dp[index][j], dp[index][j - t] + dp[v][t - 2 * right.w]);
}

int main(int, char **)
{
    cin >> s;
    read(0);
    dfs(0);
    cout << dp[0][s - 2 * nodes->w - 1];
    return 0;
}