摘要：
学习博客：https://rpdreamer.blog.luogu.org/bei-bao-wen-tif[mo+k*w[i]]=q[head]+k*c[i]；这一步骤不被理解。双方同意在末尾添加a*c[i]。罗古P1776宝藏筛选#include＜cstio＞#include˂cstring＞#include＜iostream＞#include˂algorithm＞#include˂queu
学习博客：https://rpdreamer.blog.luogu.org/bei-bao-wen-ti
f[mo+k*w[i]]=q[head]+k*c[i];
这一步没有搞懂啊，说好的最后应该加上 a*c[i] 的呢
洛谷P1776 宝物筛选
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<cmath> using namespace std; typedef long long ll; const int maxn = 100010; int n,m,ans; int head,tail; int c[maxn],w[maxn],num[maxn]; int f[maxn]; int q[maxn],pos[maxn]; ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;} int main(){ n=read(),m=read(); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++){ c[i]=read(),w[i]=read(),num[i]=read(); if(w[i]==0){ ans+=num[i]*c[i]; continue; } if(num[i]>(m/w[i])) num[i]=m/w[i]; for(int mo=0;mo<w[i];mo++){ head=1,tail=0; for(int k=0;k<=(m-mo)/w[i];k++){ int x=f[mo+k*w[i]]-k*c[i]; while(head<=tail && q[tail]<=x) tail--; q[++tail]=x; pos[tail]=k; while(head<=tail && pos[head]<k-num[i]) head++; f[mo+k*w[i]]=q[head]+k*c[i]; } } } printf("%d\n",ans+f[m]); return 0; }