信奥赛真题题解[NOIP 2005 普及组] 第三题采药

四季读书网 2026-09-28 18:57:25 5 0

商丘地区可带孩子免费体验一次编程试听课

[NOIP 2005 普及组] 采药

NOIP 2005 普及组第三题

本题是纯动态规划01背包问题，可以直接套模板使用。

状态：dp[j]表示背包容量为j时能够获得的最大价值

转移方程：dp[j]=max(dp[j] , dp[j-t[i-1]]+v[i-1])

使用了一维数组优化，代码如下：

#include<iostream>using namespace std;int T, M;int v[105], t[105];int dp[1005];intmain(){	cin>>T>>M;for(int i=0; i<M; i++) {//输入每个草药的时间和价值		cin>>t[i]>>v[i];	}for(int i=1; i<=M; i++)//遍利每一个草药for(int j=T; j>= t[i-1]; j--) //保证每个草药只取一次，j值从大到小			dp[j]=max(dp[j], dp[j-t[i-1]]+v[i-1]);	//j逆序可确保计算dp[j]时dp[j-t[i-1]]的值仍是上一轮的//从而防止同一物品被重复计算	cout<<dp[T];return 0;}

本文地址： https://sjds.net/823162.html

文章来源：四季读书网