企业网站设计与制作,上海seo博客,长沙网站设计哪家专业,wordpress获取分类文件夹正题
题目链接:https://www.luogu.org/problemnew/show/P2048 题目大意
一个长度为nnn序列aaa。寻找kkk个子序列要求长度在L∼RL\sim RL∼R之间#xff0c;求这kkk个子序列的最大和。 解题思路
首先对aaa求出前缀和数组sss。题目转换为求kkk个数对要求两两之间距离在L∼RL\…正题
题目链接:https://www.luogu.org/problemnew/show/P2048 题目大意
一个长度为nnn序列aaa。寻找kkk个子序列要求长度在L∼RL\sim RL∼R之间求这kkk个子序列的最大和。 解题思路
首先对aaa求出前缀和数组sss。题目转换为求kkk个数对要求两两之间距离在L∼RL\sim RL∼R且差最大。
因为数对之间互不影响所以显然求前kkk大的数对就好了。
我们在大根堆之中存储一个五元组(l,r,id,x,val)(l,r,id,x,val)(l,r,id,x,val)。表示对于后面的数ididid在l∼rl\sim rl∼r之间求一个xxx使得valaid−axvala_{id}-a_xvalaid−ax最大。堆以valvalval为关键字。xxx和valvalval我们可以用RMQRMQRMQ快速计算出来。
然后我们开始时对于每个iii我们将(i−R,i−L,i,x,val)(i-R,i-L,i,x,val)(i−R,i−L,i,x,val)丢入堆中。
之后执行kkk次取出对顶(l,r,id,x,val)(l,r,id,x,val)(l,r,id,x,val)使ansvalansvalansval。 然后将(l,x−1,id,x′,val′)(l,x-1,id,x#x27;,val#x27;)(l,x−1,id,x′,val′)和(x1,r,id,x′,val′)(x1,r,id,x#x27;,val#x27;)(x1,r,id,x′,val′)重新丢入堆中这样就保证了对于不同的idididxxx不会重复而且也能取到最大。
时间复杂度:O(nlog(nk)):O(n\ log\ (nk)):O(n log (nk)) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N501000;
ll n,k,L,R,lg[N],f[30][N],a[N],ans,w[30][N];
ll RMQ(ll l,ll r)
{ll zlg[r-l1];return f[z][l]f[z][r1-(1z)]?w[z][l]:w[z][r1-(1z)];
}
struct node{ll l,r,x,id,val;node(ll _l0,ll _r0,ll _id0){l_l;r_r;id_id;xRMQ(l,r);vala[id]-a[x];}
};
bool operator (const node a,const node b)
{return a.valb.val;}
priority_queuenode q;
int main()
{scanf(%lld%lld%lld%lld,n,k,L,R);lg[0]-1;for(ll i1;in;i){scanf(%lld,a[i]);a[i]a[i-1];f[0][i]a[i];w[0][i]i;lg[i]lg[i/2]1;}for(ll i1;(1i)n;i)for(ll j0;j(1i)-1n;j){if(f[i-1][j(1i-1)]f[i-1][j])w[i][j]w[i-1][j(1i-1)];elsew[i][j]w[i-1][j];f[i][j]min(f[i-1][j],f[i-1][j(1i-1)]);}for(ll iL;in;i)q.push(node(max(i-R,0ll),i-L,i));while(k--){node zq.top();ansz.val;q.pop();if(z.xz.l) q.push(node(z.l,z.x-1,z.id));if(z.xz.r) q.push(node(z.x1,z.r,z.id));}printf(%lld,ans);
}
