Gym - 101981B Tournament (WQS二分+单调性优化dp)

题意：x轴上有n个人，让你放置m个集合点，使得每个人往离他最近的集合点走，所有人走的距离和最短。

把距离视为花费，设$dp[i][k]$表示前i个人分成k段的最小花费，则有递推式$dp[i][k]=min\{dp[j][k-1]+w(j,i)\}$，其中$w(j,i)$可以$O(1)$求出。

显然，如果考虑段数的话，光状态数就有n^2个，肯定行不通。不过这题的最优解对段数的函数是凸的，因此可以用WQS二分来打破段数的限制。

给每个集合点加上一个额外的花费c，然后忽略段数的限制，这样递推式就变成了$dp[i]=min\{dp[j]+w(j,i)\}+c$，这个递推式满足“决策单调性”，即如果i是由j转移而来，而i'>i，则j'>=j。这种dp是有一定的套路的，利用单调队列维护可能成为最优决策点的点以及它的左右边界，中间过程中需要不断地“掐头去尾”，及时弹出队首已经废掉的决策点，每push进一个结点，需要弹出队尾不如它优的决策点，并修改队尾的右边界，保证队首总是最优决策点。值得注意的是这道题的最优决策边界不像斜率优化那样明显可以直接算出来，也需要通过二分来确定。

然后在dp的过程中记录段数cnt[n]，如果最优解分成了k段，那么dp[n]-k*c就是在划分为k段的条件下的最优解。根据k与m的大小关系进行二分，直到最优解恰好分成了m段为止。

你如果问为什么满足凸性和决策单调性？蒟蒻表示不会证，反正凭经验和直觉猜就对了，或者打表~~

复杂度$O(nlognlogA)$，这道题还要和卡常斗智斗勇，算法常数过大会T，变量全开longlong也会T...

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=3e5+,inf=0x3f3f3f3f;

 int n,m,hd,tl,a[N],q[N],cnt[N],L[N],R[N];

 ll S[N],dp[N],k;

 ll sum(int l,int r) {return S[r]-S[l-];}

 ll w(int i,int j) {

     ++i;

     return sum((i+j+)>>,j)-sum(i,(i+j-)>>)+k;

 }

 int fd(int j,int k) {

     int ret=R[k]+,l=L[k],r=R[k];

     while(l<=r) {

         int mid=(l+r)>>;

         if(dp[j]+w(j,mid)<=dp[k]+w(k,mid))ret=mid,r=mid-;

         else l=mid+;

     }

     return ret;

 }

 int solve() {

     hd=tl=,L[]=,R[]=n,q[tl++]=;

     for(int i=; i<=n; ++i) {

         for(; hd<tl&&R[q[hd]]<i; ++hd);

         dp[i]=dp[q[hd]]+w(q[hd],i);

         cnt[i]=cnt[q[hd]]+;

         for(; hd<tl&&dp[i]+w(i,L[q[tl-]])<=dp[q[tl-]]+w(q[tl-],L[q[tl-]]); --tl);

         L[i]=(hd<tl?fd(i,q[tl-]):i+),R[i]=n;

         if(hd<tl)R[q[tl-]]=L[i]-;

         q[tl++]=i;

     }

     return cnt[n];

 }

 ll bi(ll l,ll r) {

     ll ret;

     while(l<=r) {

         ll mid=(l+r)>>;

         k=mid;

         if(solve()>=m)ret=dp[n]-m*k,l=mid+;

         else r=mid-;

     }

     return ret;

 }

 int main() {

     scanf("%d%d",&n,&m);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)S[i]=S[i-]+a[i];

     printf("%lld\n",bi(,S[n]+));

     return ;

 }

巴特西

Gym - 101981B Tournament (WQS二分+单调性优化dp)

最新文章

热门文章