正题

题目链接:https://loj.ac/p/6039

---

题目大意

有\(n\)个物品，第\(i\)个费用为\(w_i\)，价值为\(v_i\)，对于\(k\in[1,m]\)求费用为\(m\)时能获得的最大价值。

\(1\leq n\leq 10^6,1\leq m\leq 5\times 10^4,1\leq w_i\leq 300,1\leq v_i\leq 10^9\)

---

解题思路

好早以前写的不过不知道为啥错了，现在来补个新的。

\(w_i\)很小，考虑以其为突破口，显然地我们可以把\(w_i\)相同的按照\(v_i\)从大到小排序，那么对于每个\(w_i\)，我们就可以选择若干个。

设\(f_{i,j}\)表示做到\(w=i\)时费用为\(j\)的最大价值和，那么有

\[f_{i,j}=f_{i-1,j-ki}+s_{i,z} \]

（\(s_{i,z}\)表示\(w=i\)的物品中前\(z\)大的价值和）

这个式子很难用常规的优化，但是可以用四边形不等式。至于证明，我们有\(w_{i,j}=s_{j-i}\)
要证明

\[w_{i,j}+w_{i+1,j+1}\geq w_{i,j+1}+w_{i+1,j} \]

\[s_{j-i}+s_{j-i}\geq s_{j-i+1}+s_{j-i-1} \]

然后因为\(s_{i+1}-s_{i}\)是递减的，所以成立。

那么我们现在对于每个枚举的\(w=i\)，把所有的\(ik+j(\ j\in[0,i)\ )\)都分成一组。

然后对于每一组我们都用四边形不等式优化，不过我忘了优化的方法了，还是记一下吧：

对于所有的可能的决策我们用一个单调队列记录，顺带记录\(z_i\)表示队列里第\(i\)个决策和第\(i+1\)个决策的交叉点（在\(z_i\)之前\(q_{i}\)更优，\(z_i\)以之后\(q_{i+1}\)更优）。

然后每次弹出队列前面的来找答案，加入的时候我们就二分出队尾和新加入的决策交换点，然后一直弹尾部直到不交叉。

时间复杂度：\(O(mw\log m)\)

---

code

#include
#include
#include
#include
#define ll long long
using namespace std;
const ll N=5e4+10;
ll n,m,g,f[2][N],q[N],z[N];
vector w[310];
bool cmp(ll x,ll y)
{return x>y;}
ll calc(ll i,ll j,ll p,ll k)
{return f[!g][i*p+k]+w[p][j-i-1];}
ll bound(ll i,ll j,ll p,ll k){
	ll l=i+1,r=(m-k)/p;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(calc(i,mid,p,k)=bound(i,q[tail],p,k))tail--;
				z[tail]=bound(i,q[tail],p,k);q[++tail]=i;
			}
		}
	}
	for(ll i=1;i<=m;i++)
		printf("%lld ",f[g][i]);
	return 0;
}