找回密码
 立即注册
查看: 18|回复: 0

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

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:15
  • 打卡月天数:1
  • 打卡总奖励:117
  • 最近打卡:2025-08-02 15:29:27

21

主题

5

回帖

2388

积分

VIP

积分
2388
发表于 2025-7-18 16:53:50 | 显示全部楼层 |阅读模式
一、解题思路:
‌问题分析‌:给定背包容量T和M个物品(草药),每个物品有采摘时间t和价值v,求在限定时间内能获得的**价值。
‌状态定义‌:定义dp[j]表示前i个物品在时间j限制下的**价值。
状态转移‌:
若当前物品时间超过剩余时间:dp[j] = dp[i-1][j]
否则:dp[j] = max(dp[i-1][j], dp[i-1][j-t] + v)。
优化‌:使用滚动数组将空间复杂度从O(NV)降为O(V),需逆序遍历时间。
二、代码实现:
  1. #include<bits/stdC++.h>
  2. using namespace std;

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

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

  10.     // 动态规划核心
  11.     for(int i = 1; i <= M; i++) {
  12.         for(int j = T; j >= t[i]; j--) {  // 逆序遍历防止重复计算
  13.             dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
  14.         }
  15.     }
  16.     cout << dp[T];  // 输出**价值
  17.     return 0;
  18. }
复制代码

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

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表