题目大意

厨师 Bajtazar 需要处理 $n$ 份订单，初始能量为 $e$。对于剩余 $k$ 份订单，可以选择以下操作：

1. 取1份：耗时 jeden(k)，能量 $+1$
2. 取2份：耗时 dwa(k)，能量不变（要求 $k > 1$）
3. 取一半：耗时 polowa(k)，能量 $-1$（要求 $k > 1$）

能量不能低于 $0$，求完成所有订单的最短时间。

解题思路

问题分析

这是一个典型的动态规划问题，具有以下特点：

• 最优子结构：完成 $k$ 份订单的最优解依赖于完成更少订单的最优解
• 状态空间：状态为 (剩余订单数, 当前能量)
• 状态转移：每个状态最多有3种转移方式

状态定义

设 dp[k][e] 表示剩余 $k$ 份订单、当前能量为 $e$ 时的最小完成时间。

状态转移方程

对于状态 (k, e)：

1. 取1份（始终可用）：

   dp[k][e] = min(dp[k][e], jeden(k) + dp[k-1][e+1])
   

2. 取2份（当 k > 1）：

   dp[k][e] = min(dp[k][e], dwa(k) + dp[k-2][e])
   

3. 取一半（当 k > 1 且 e > 0）：

   dp[k][e] = min(dp[k][e], polowa(k) + dp[k - k/2][e-1])
   

边界条件

• dp[0][e] = 0：没有订单时时间为0
• 对于不合法状态（能量为负或订单数为负），设为无穷大

算法实现

记忆化搜索

#include "ckuclib.h"
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 2e9;
vector<vector<int>> memo;

int solve(int k, int e) {
    if (k == 0) return 0;
    if (e < 0) return INF;
    if (memo[k][e] != -1) return memo[k][e];
    
    int res = INF;
    
    // 操作1：取1份
    res = min(res, jeden(k) + solve(k-1, e+1));
    
    // 操作2：取2份（需要k>1）
    if (k > 1) {
        res = min(res, dwa(k) + solve(k-2, e));
    }
    
    // 操作3：取一半（需要k>1且e>0）
    if (k > 1 && e > 0) {
        int take = k / 2;
        res = min(res, polowa(k) + solve(k - take, e-1));
    }
    
    return memo[k][e] = res;
}

int main() {
    int n = dajn();
    int e = daje();
    
    memo.assign(n+1, vector<int>(n+e+2, -1));
    
    int ans = solve(n, e);
    odpowiedz(ans);
    
    return 0;
}

迭代DP（推荐用于大数据）

#include "ckuclib.h"
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 2e9;

int main() {
    int n = dajn();
    int e = daje();
    
    // dp[k] 表示剩余k份订单时的最小时间（需要记录能量维度）
    // 由于能量最多可能达到 n+e，我们使用二维DP
    vector<vector<int>> dp(n+1, vector<int>(n+e+2, INF));
    
    // 初始化边界
    for (int energy = 0; energy <= n+e+1; energy++) {
        dp[0][energy] = 0;
    }
    
    // 按订单数从小到大计算
    for (int k = 1; k <= n; k++) {
        for (int energy = 0; energy <= n+e+1; energy++) {
            // 操作1：取1份
            if (energy + 1 <= n+e+1) {
                dp[k][energy] = min(dp[k][energy], jeden(k) + dp[k-1][energy+1]);
            }
            
            // 操作2：取2份
            if (k >= 2) {
                dp[k][energy] = min(dp[k][energy], dwa(k) + dp[k-2][energy]);
            }
            
            // 操作3：取一半
            if (k >= 2 && energy > 0) {
                int take = k / 2;
                dp[k][energy] = min(dp[k][energy], polowa(k) + dp[k-take][energy-1]);
            }
        }
    }
    
    odpowiedz(dp[n][e]);
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \times (n+e))$，对于子任务3的 $n, e \leq 10^6$ 来说太大
• 空间复杂度：$O(n \times (n+e))$

优化思路

对于大数据范围（$n, e \leq 10^6$），需要优化：

1. 状态压缩：观察发现能量变化有规律，可以优化状态表示
2. 贪心性质：分析三种操作的成本效益，优先选择性价比高的操作
3. 数学优化：寻找问题的数学性质，减少状态数量

总结

本题是典型的动态规划问题，主要考察：

• 状态设计和转移方程的建立
• 边界条件的处理
• 对交互题型的适应能力
• 在大数据下的优化思维

算法标签：动态规划、记忆化搜索、最优化问题、交互题