P1776 宝物筛选

本文主要是介绍P1776 宝物筛选，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[题目通道](宝物筛选 - 洛谷)

#include<bits/stdc++.h>
#define int long long 
#define fast register intusing namespace std;const int maxn=100000+10;int dp[maxn],v[maxn],w[maxn],m[maxn],n,V; int q[maxn],q2[maxn],L,R; signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>V;for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>m[i];for (fast i=1;i<=n;i++){for (fast r=0;r<w[i];r++){L=1; R=0;for (fast k=0;r+k*w[i]<=V;k++){if (L<=R && k-q[L]>m[i]) L++;while (L<=R && dp[r+k*w[i]]-k*v[i]>=q2[R]) R--;q[++R]=k;q2[R]=dp[r+k*w[i]]-k*v[i];dp[r+k*w[i]]=q2[L]+k*v[i];} } }cout<<dp[V];return 0;
}

这篇关于P1776 宝物筛选的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---