本文主要是介绍P1616 疯狂的采药(完全背包模板),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
//这是一道完全背包的题,并且需要用一维数组优化空间,否则会MLE
#include <bits/stdc++.h>
using namespace std;
//t表示可以用来采药的时间(相当于背包容量)
//m表示草药的数目(相当于物品数量)
int t, m; //m<=10^4,t<=10^7
//w[i]表示采摘第i种草药需要花费的时间(相当于背包模型中物品的体积)
//v[i]表示第i种草药的价值(相当于背包模型中物品的价值)
int w[10001], v[10001]; //w[j]<=10^4, v[j]<=10^4
//dp[j]表示在j时间内,可以采摘到的最大价值,那么dp[t]就是我们想要的答案
long long dp[10000001]; //int会爆掉,特例:t=10^7,m=1,w[1]=1,v[1]=10^4,dp[1]=10^11
int main()
{ //t表示可以用来采药的时间,m表示草药的数目 cin >> t >> m;for(int i=1; i<=m; ++i){cin >> w[i] >> v[i];} //遍历草药 for(int i=1; i<=m; ++i){//每种草药可以重复采摘,所以顺序 for(int j=w[i]; j<=t; ++j){//采摘第i种草药和不采摘第i种草药种选一个最大的 dp[j]=max(dp[j], dp[j-w[i]]+v[i]);} }cout << dp[t];return 0;
}
这篇关于P1616 疯狂的采药(完全背包模板)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!