集训队作业解题报告2炸弹

《蓝猫炸弹》解题2号就把它们的位置用一个数来表示，这个数就是这一个炸弹与最左边炸弹的距离，每一个炸弹i都有一个“威力值”si。如2i，那么它的威力就会向直线的两边扩散。最开si1，如果到0了，这个威力就消失了。如果在威力没有消失的时候，2k2号找到了你，要你为他解决这个问题。[输入n，k(1<=n<=10000，1<=k<=100第二行有np1,p2……pn，表示这n个炸弹的位置，用它与第一个炸弹的0=p1<p2<p3<……<pn<=109。第三行有n个数s1,s2,s3sn从左到右表示这n个炸弹的威力值，1<=si<=109[输出[输入样例602561111422[输出样例5 41、2、3、4个炸弹都爆了；然后再引爆565个炸弹，这已经是最多的了。i的引爆范围用[Li,Ri]表示，它表示直接i后，LiRi显然有1≤Li≤i≤Ri≤n

iijRi=min{j|j≥i,Sj-Si-1≤Pj-Pi}。来看下面的结论①i<j，Lj≤iLj≤Liji的jijLi②如果炸弹ijji，ij的引爆范围。jii，威力强度大于siisi，所以前者向左传播的范围更远。根据定Sj-Si>pj-pi所以对于k<i，如果有Si-Sk>pi-pk(Si-Sk)+(Sj-Si)>(pi-pk)+(pj-pi)，即Sj-Sk>pj-pk。Re(i,j)i,je(i,j)，它们都是直接引爆的，那么可以把这次爆炸序列位于i与j之间的炸弹从引爆序列中删掉。这时，到了直接引爆i后，j会引爆，j的范围大了。这是不是有利的？是的，虽然这ji的前ji，这样效果也不比原来的i，je(i,j)Li=max{j|j<i,Si-Sj≤pi-pj}+1jLi=1。变一下形，Li=max{j|j<i,Si-pi≤Sj-pj}+1wi=Si-piLi=max{j|j<i,wi≤wj}+1。从Li0<x<y<iwx≤wyii以后的数的L值都不可能是x了，所以，只需要维护一个表，保存一列数i1<i2<i3<……<it,wi1>wi2>……>witLiwiwi添到表后。这L值只需要O(n)的时间复杂度。LRk个炸弹使得引爆的炸弹数尽量的多。通过前面的分析，只需要求出一个炸弹的集合S，|S|≤k，并且对于S中任意两个不同元素i,j，e(i,j),e(j,i)都不成立。由于与顺序无关，所以可以从左到右选择S中的元素，不难发现，如果已经选择了i个炸弹，那么后面的决策只会与f[i,j]ij时最多引爆的炸f[i,j]=max{f[i-1,x]+Rj-Lj+1-|Inter[j∩Inter[x]|,x<j,~e(x,j),~(j,x)}。其中Inter[j]LjRjO(kn2)，上面的方程中，x<j,Rx,L。Inte[j]∩Inte[]R[]<Lj][L,x]。既然有两xX1X2xInte[]Inte[j]没有交集，X2xInte[]Inte[j]有交集，为了方便，1..nX3X1X2jX1,X2呢？似乎很难因为当j增大1时，Lj的变化难以把握元素可以从X3X2中，X2X1中，也可以从X1X2，X2X3，甚至可以从X1X3,X3X1，LL变化有规律一些呢？这个思路是可以的，具体来说，就是不按j从小往大计算f[i,j]，而是按照Lj从小到大f[i,j]，这样能不能行得通呢？首先，上面的规划是满足拓扑顺序的，即保证了如果Lx≥Lj，那么在计算jX1X2X2X3中的传递是双向的，如果直接维护两个集X2X3的传递是双向的，所以我们干脆不把它们分开。现在来重新划分集合：(j而言)X1X3的元素对方有一个很明显的区别，那就是：RxjjX2中的x，只要有Lj≤Rx<j，那么它就会方程有影响！而需要计算的x的R值是处R为序来建一棵线段树，那么，线段树x∈X2，那么会有方程：f[i,j]=max{f[i-1,x]+Rj-Rx,x∈X2}，由于Rj可以移出来，所以对于X2中的元素L再来总结一下整个算法，首先用O(n)的时间复杂度计算出每一个炸弹的L，Rf[i-1]f[i]max1（不需要Rx<LjxX1中（max1x<Ljx加RxLjj-1f[i-1,x]-RxRj值。那么需不需要Lj>RxxX2中计算也X2O(knlog2n)。1.70GHzFreePascalv1.0.6)。问题是否就此解决了呢？算法有没有进一步优化呢？能不能从O(knlog2n)降到[参考文献 ——刘汝佳黄亮[讨论在与肖天的讨论中否决了O(kn)的算法，只好用O(knlog2n)的了[感谢inputfile='bomb.in';arr=array[0..maxn]oflongint; arrabsoluteaddress1; arrabsolute arrabsolute arrabsolute arrabsolute arrabsolute arrabsolute arrabsolute arrabsolute arrabsoluteaddress6;tree:array[1..231072]oflongint;procedureinit;②开始时，认为如果e(i,j)&~e(j,i)，那么就不会选取j，这样就得到了O(kn)的算法，但是很快被xiaotian找fori:=1tondoread(p[i]);fori:=1tondoread(s[i]);whilen1<ndon1:=n1shl1;fori:=1tondototals[i]:=totals[i-1]+s[i]procedureprepare;fori:=1tondowhile(top>0)and(totals[i]-p[i]>totals[q[top]]-p[q[top]])dodec(top);iftop=0thenleft[i]:=1elseleft[i]:=q[top]+1;fori:=ndownto1dowhile(top>0)and(totals[i-1]-p[i]<totals[q[top]-1]-p[q[top]])doiftop=0thenright[i]:=nelseright[i]:=q[top]-1;procedurepreparelist(varkey,list:arr);proceduresort(l,r:longint);k:=key[list[(i+r)shr1]];whilei<=jdobeginwhilekey[list[i]]<kdoinc(i);whilekey[list[j]]>kdodec(j);ifi<=jthenbeginifl<jthensort(l,j);ifi<rthenfori:=1tondolist[i]:=i;functiongetmaxoftree(l,r:longint):longint;ifl>rthenbegingetmaxoftree:=-maxlongint;exitend;ifl=rthenbegingetmaxoftree:=tree[n1+l];exitend;k:=1;len:=n1+1;left:=1;right:=n1+1;mid:=(left+right)shr1;while(l>mid)or(r<mid+1)dobeginifl>midthenbeginleft:=mid+1;k:=kshl1+1elsebeginright:=mid;k:=kshl1len:=lenshrmid:=(left+right)shr1k1:=kshl1;len1:=lenshr1;whileleft<=middoifmid-left+1>=len1theniftree[k1]>tmpthentmp:=tree[k1];k1:=k1shllen1:=len1shr1k1:=kshllen1:=lenshrwhilemid+1<=rightdoifright-mid>=len1theniftree[k1]>tmpthentmp:=tree[k1];k1:=k1shllen1:=len1shr1procedurerefreshtree(k,d:longint);whilek>0doifd>tree[k]thentree[k]:=d;k:=kshr1procedurework;fori:=1tondof[i]:=right[i]-left[i]+1;fors:=2tomdobeginfilldword(tree,sizeof(tree)shr2,$80000000);forplistl:=1tondobeginwhilepm<left[i]dobeginwhileright[listr[plist