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

深度学习
• 阅读 51

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),适用于题目约束范围。

参考:竞赛学习

点赞
收藏
评论区
推荐文章
美凌格栋栋酱 美凌格栋栋酱
6个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
Kubrnete Kubrnete
4年前
完全背包问题
问题描述有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v\i\,体积为w\i\,求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可
贾蔷 贾蔷
1个月前
洛谷P1255题 解题思路和步骤 C++实现带注释,c++入门基础题
一、问题描述与递推关系建立洛谷P1255数楼梯问题要求计算n级台阶的不同走法数,每次可以跨1级或2级。这本质上是斐波那契数列的变种问题,递推公式为f(n)f(n1)f(n2)。当n≤50时可用普通整型存储,但题目中n可能达到5000,这就必须使用高精度运
贾蔷 贾蔷
1个月前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
深度学习 深度学习
1个月前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
1个月前
动态规划进阶:牛客4802题带附件背包问题详解 | 组合优化技巧
一、问题背景与算法思路牛客4802题是一个典型的带附件的背包问题变种,要求在主件和附件存在依赖关系的情况下,选择物品组合使总价值最大化。本文通过动态规划方法,将问题转化为分组背包问题,通过预处理所有可能的组合方式来实现高效求解。二、完整代码实现(带详细注释
深度学习 深度学习
1个月前
2012年NOIP提高组「借教室」(洛谷P1083)解题思路与二分查找优化代码解析
一、题目解读本题为2012年NOIP提高组中的「借教室」问题(洛谷P1083),要求处理教室借用订单的分配问题。给定n天每天可用教室数量r和m个订单(订单包含需求教室数d、开始日期s、结束日期t),判断能否通过删除部分订单使所有订单满足教室容量限制。若能,
贾蔷 贾蔷
2星期前
洛谷P1102题解:利用哈希表优化的数对统计 C++代码解析
一、题目解读P1102题要求处理一组整数与常数C,统计数组中是否存在元素A与B满足ABC。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。二、解题思路采用(unorderedmap)实现高效统计。首先遍
贾蔷 贾蔷
1星期前
力扣15题三数之和解法(C++双指针算法详解)
一、题目解读15题()要求在一个包含n个整数的中,找出所有三个数之和为0的组合,且每个组合的元素不能重复。题目考察数组遍历、与技巧的结合,是经典的多问题,对时间复杂度优化有较高要求。二、解题思路采用“双指针”策略:首先对原数组排序,然后固定第一个数,通过左
贾蔷 贾蔷
2个月前
NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析
一、题目描述简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。二、解题思路与算法分析1.问题分析1.问题核心是求解两条不交