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; }
P13015 [GESP202506 六级] 学习小组
//完全背包模型 #include <iostream> using namespace std; int n, a[1010], dp[1010]; int main() { scanf("%d", &n); for(int i=1; i<=n; ++i){ scanf("%d", &a[i]); } //枚举物品, i 个人组成的小组可以看为一个物品，他占的空间为 i，他的价值为 a[i] for(int i=1; i<=n; ++i){ //枚举背包容量, 每个物品可以多次拿, 完全背包模型, 顺序 for(int j=i; j<=n; ++j){ dp[j]=max(dp[j], dp[j-i]+a[i]); } } printf("%d\n", dp[n]); return 0; }
P10721 [GESP202406 六级] 计算得分 完全背包
#include<iostream> using namespace std; int n, a[21], m, dp[33334], cnt, ans; string s; int main() { cin >> n; for(int i=1; i<=n; ++i){ cin >> a[i]; } cin >> m; cin >> s; for(int i=1; i<=n; ++i){ for(int j=i; j<=m/3; ++j){ dp[j]=max(dp[j], dp[j-i]+a[i]); } } for(int i=0; i<=m-3;){ if(s[i]=='a' && s[i+1]=='b' && s[i+2]=='c'){ cnt++; i+=3; } else{ ans+=dp[cnt]; cnt=0; i++; } } ans+=dp[cnt]; cout << ans << endl; return 0; }
