发现时间并不重要,不妨设 T 为离散化之后最大的时间。
设在 [i,j] 中有 wi,j 个活动被包含,容易 O(n3) 求解。
设 fi,j 表示 [1,i] 的时间中有 j 个活动在第 1 个场地举行,第 2 个场地举行活动的最大值。
那么有转移方程:
fi,j=k=1maxi−1(fk,j+wk,i,fk,j−wk,i)
设 gi,j 表示 [i,T] 的时间中有 j 个活动在第 1 个场地举行,第 2 个场地举行活动的最大值。
同理,有转移方程:
gi,j=k=i+1maxT(gk,j+wk,i,gk,j−wk,i)
预处理的时间复杂度为 O(n3)。
那么第 1 问的答案就显然是:j=1maxnmin(fT,j,j)。
下面考虑固定一个活动的情况。
显然可以得到这个区间的左右端点 L,R,那么枚举前后第 1 个场地分别举办了多少比赛:
AnsL,R=x=0maxw1,Ly=1maxwR,Tmin(x+wL,R+y,fL,x+gR,y)
发现如果固定 i,那么fi,j 和 gi,j 的值随 j 的值减增大而减小,所以当 i 增加时 j 应该尽可能的减少。
考虑维护双指针,那么时间复杂度为 O(n3)。