D 档案分册长度为n的序列ci,wic_i,w_ici,wi分成k段每段非空cic_ici相同一组求wiw_iwi和最大段最小值。无解-1。二分答案。#includebits/stdc.h#defineFor(i,n)for(inti1;in;i)#defineForD(i,n)for(intin;i1;i--)#defineFork(i,k,n)for(intik;in;i)#defineRep(i,n)for(inti0;in;i)#definegmin(a,b)amin(a,b);#definegmax(a,b)amax(a,b);#definepbpush_backusingnamespacestd;typedeflonglongll;ll a[510][510],f[510][510];intmain(){intT1;while(T--){intn,k;cinnk;vectorllc(n1),w(n1,0);For(i,n)cinc[i]w[i];vectorlll(n1,1e9),r(n1,0),s(n1,0);For(i,n){gmin(l[c[i]],(ll)i)gmax(r[c[i]],(ll)i)}For(i,n)if(l[i]!1e9){s[l[i]],s[r[i]]--;}For(i,n)s[i]s[i-1];ll x0;vectorllnw;For(i,n){xw[i];if(!s[i])nw.push_back(x),x0;}if(x)nw.pb(x);// for(auto p:nw) coutp ;coutendl;if((nw.size())k){puts(-1);}else{ll l0,r0;for(autop:nw){rp;gmax(l,p)}ll ansr;while(lr){ll m(lr)/2,c1,x0;for(autop:nw){if(xpm)xp;elsexp,c;}if(ck)ansm,rm-1;elselm1;}coutansendl;}}return0;}F 未竟之志长度为n的序列aia_iai拿走一个数塞到任意位置求此时连续5个数的和最大值。考虑有数拿走有数添进来没影响3种情况#includebits/stdc.h#defineFor(i,n)for(inti1;in;i)#defineForD(i,n)for(intin;i1;i--)#defineFork(i,k,n)for(intik;in;i)#defineRep(i,n)for(inti0;in;i)#definegmin(a,b)amin(a,b);#definegmax(a,b)amax(a,b);usingnamespacestd;typedeflonglongll;ll a[510][510],f[510][510];intmain(){intT;cinT;while(T--){intn;cinn;vectorlla(n1),s(n1,0),pr(n1,-1e9-1),sf(n10,-1e9-1);For(i,n)cina[i];For(i,n)s[i]a[i]s[i-1],pr[i]max(a[i],pr[i-1]);ForD(i,n)sf[i]max(a[i],sf[i1]);ll anss[5];Fork(i,5,n)gmax(ans,s[i]-s[i-5])Fork(i,6,n){ll ts[i]-s[i-6];Fork(j,i-5,i)gmax(ans,t-a[j])}Fork(i,4,n){ll ts[i]-s[i-4];ll qmax(pr[i-4],sf[i1]);gmax(ans,tq)}coutansendl;}return0;}
