NOIP 2005 普及组 洛谷1048题 解题思路和步骤 C++实现带注释

解题思路：

‌问题分析‌：给定背包容量T和M个物品（草药），每个物品有采摘时间t[i]和价值v[i]，求在限定时间内能获得的最大价值。

‌状态定义‌：定义dp[i][j]表示前i个物品在时间j限制下的最大价值。

‌状态转移‌：

若当前物品时间超过剩余时间：dp[i][j] = dp[i-1][j]

否则：dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + v[i])。

‌优化‌：使用滚动数组将空间复杂度从O(NV)降为O(V)，需逆序遍历时间。

代码实现：

#include<bits/stdC++.h>
using namespace std;

int main() {
    int T, M;  // 总时间和草药数量
    cin >> T >> M;
    int t[105], v[105];  // 时间和价值数组
    int dp[1005] = {0};  // 滚动数组优化

    for(int i = 1; i <= M; i++) 
        cin >> t[i] >> v[i];

    // 动态规划核心
    for(int i = 1; i <= M; i++) {
        for(int j = T; j >= t[i]; j--) {  // 逆序遍历防止重复计算
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
        }
    }
    cout << dp[T];  // 输出最大价值
    return 0;
}

代码通过滚动数组优化空间，逆序遍历确保每个物品只被计算一次，时间复杂度O(MT)，适用于题目约束范围。