网站建设的客户怎么找,城市维护建设税在哪个网站申报,怎么做公司免费网站,学校网站代码模板正题
题目链接:https://loj.ac/p/6039 题目大意
有nnn个物品#xff0c;第iii个费用为wiw_iwi#xff0c;价值为viv_ivi#xff0c;对于k∈[1,m]k\in[1,m]k∈[1,m]求费用为mmm时能获得的最大价值。 1≤n≤106,1≤m≤5104,1≤wi≤300,1≤vi≤1091\leq n\leq 10^6,1\leq…正题
题目链接:https://loj.ac/p/6039 题目大意
有nnn个物品第iii个费用为wiw_iwi价值为viv_ivi对于k∈[1,m]k\in[1,m]k∈[1,m]求费用为mmm时能获得的最大价值。
1≤n≤106,1≤m≤5×104,1≤wi≤300,1≤vi≤1091\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^91≤n≤106,1≤m≤5×104,1≤wi≤300,1≤vi≤109 解题思路
好早以前写的不过不知道为啥错了现在来补个新的。
wiw_iwi很小考虑以其为突破口显然地我们可以把wiw_iwi相同的按照viv_ivi从大到小排序那么对于每个wiw_iwi我们就可以选择若干个。
设fi,jf_{i,j}fi,j表示做到wiwiwi时费用为jjj的最大价值和那么有 fi,jfi−1,j−kisi,zf_{i,j}f_{i-1,j-ki}s_{i,z}fi,jfi−1,j−kisi,z si,zs_{i,z}si,z表示wiwiwi的物品中前zzz大的价值和
这个式子很难用常规的优化但是可以用四边形不等式。至于证明我们有wi,jsj−iw_{i,j}s_{j-i}wi,jsj−i 要证明 wi,jwi1,j1≥wi,j1wi1,jw_{i,j}w_{i1,j1}\geq w_{i,j1}w_{i1,j}wi,jwi1,j1≥wi,j1wi1,j sj−isj−i≥sj−i1sj−i−1s_{j-i}s_{j-i}\geq s_{j-i1}s_{j-i-1}sj−isj−i≥sj−i1sj−i−1 然后因为si1−sis_{i1}-s_{i}si1−si是递减的所以成立。
那么我们现在对于每个枚举的wiwiwi把所有的ikj(j∈[0,i))ikj(\ j\in[0,i)\ )ikj( j∈[0,i) )都分成一组。
然后对于每一组我们都用四边形不等式优化不过我忘了优化的方法了还是记一下吧
对于所有的可能的决策我们用一个单调队列记录顺带记录ziz_izi表示队列里第iii个决策和第i1i1i1个决策的交叉点在ziz_izi之前qiq_{i}qi更优ziz_izi以之后qi1q_{i1}qi1更优。
然后每次弹出队列前面的来找答案加入的时候我们就二分出队尾和新加入的决策交换点然后一直弹尾部直到不交叉。
时间复杂度O(mwlogm)O(mw\log m)O(mwlogm) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
const ll N5e410;
ll n,m,g,f[2][N],q[N],z[N];
vectorll w[310];
bool cmp(ll x,ll y)
{return xy;}
ll calc(ll i,ll j,ll p,ll k)
{return f[!g][i*pk]w[p][j-i-1];}
ll bound(ll i,ll j,ll p,ll k){ll li1,r(m-k)/p;while(lr){ll mid(lr)1;if(calc(i,mid,p,k)calc(j,mid,p,k))lmid1;else rmid-1;}return l;
}
signed main()
{freopen(jewelry.in,r,stdin);freopen(jewelry.out,w,stdout); scanf(%lld%lld,n,m);for(ll i1,c,v;in;i){scanf(%lld%lld,c,v);w[c].push_back(v);}g0;for(ll p1;p300;p){if(w[p].empty())continue;g^1;memcpy(f[g],f[!g],sizeof(f[g]));
// memset(f[g],0,sizeof(f[g]));sort(w[p].begin(),w[p].end(),cmp);while(w[p].size()m/p)w[p].push_back(0);for(ll i1;iw[p].size();i)w[p][i]w[p][i-1];for(ll k0;kp;k){ll head1,tail0;for(ll i0;i*pkm;i){while(headtailz[head]i)head;if(headtail)f[g][i*pk]max(f[g][i*pk],calc(q[head],i,p,k));while(headtailz[tail-1]bound(i,q[tail],p,k))tail--;z[tail]bound(i,q[tail],p,k);q[tail]i;}}}for(ll i1;im;i)printf(%lld ,f[g][i]);return 0;
}
