讲道题GESP202506六级 学习小组
2025-12-24 13:16:00
发布于：上海
4阅读
0回复
0点赞
今天闲来无事，来讲一道GESP六级题 其实是因为看到自己的99个粉丝，想涨几个粉丝拿到称号“出道萌新”
P13015 [GESP202506 六级] 学习小组（详见洛谷）
题目传送门
先读题：
阿巴阿巴阿巴阿巴（省略）
读完了，首先肯定是DP动态规划
可是不会写方程式！（就是我）
可是当我再读了一遍后
这不就是背包吗？
把背包容量看成n，物品数量也是n，积极度就是价值，几个人就是价值对应的重量
于是此时的你：Ctrl+A，Ctrl+C，Ctrl+V
直接把背包复制过来，然后稍微改一下
#include<bits/stdc++.h>
using namespace std;
int dp[10100],w[11000],c[11000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
w[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
if(j>=w[i]){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
}
cout<<dp[n];
return 0;
}
然后输入验证码，提交！
WAWAWAWAWAWAWAWAWAWAWAWAWA
啊啊啊啊啊啊啊啊啊啊啊————我**************（当时本人be like）
然后又看了一遍
才发现
这是完全背包啊！
至此，题目结束！
AC代码：
#include<bits/stdc++.h>
using namespace std;
int dp[10100],w[11000],c[11000];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
w[i]=i;
}
for(int i=1;i<=n;i++){/
for(int j=n;j>=1;j--){
for(int k=0;k<=j/w[i];k++){
dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
}
}
}
cout<<dp[n];
return 0;
}
都看到这了，求求了，
点个赞+关注把！！！！
这里空空如也
有帮助，赞一个