P5574 [CmdOI2019] 任务分配问题

思路

首先，我们很好得出这种分段问题的状态转移方程即其中 表示选到前 个数，分了 段的最小费用，我们可以用 的时间复杂度来实现，显然超时，得分20pts。

接着考虑优化，不难发现，，所以，该式子满足四边形不等式，即可使用决策单调性来优化该状态转移方程。

P4767邮局这道题，与该题状态转移方程相同，所以一上手想到使用四边形不等式中 的性质优化该题优化该题，然而，这种算法时间复杂度为 ，并不能通过该题，结果超时，得分40pts，邮局一题中 与 上界相同，而该题 远小于 我们需要使用分治优化将时间复杂度降到 级别才能通过。

我们解决了DP阶段的问题，接着需要解决的就是预处理 数组的问题了，由于我们无法接受 的时间复杂度，所以我们要对其进行优化，因为数组大小的限制，预处理出 数组这条思路已经行不通了，我们考虑在DP过程中求一段的花费，注意到，在分治求解的过程中，当决策点每向右移动一位，我们的费用由 变为 过程中，我们增加的顺序对费用即为 到 中小于 的数的个数，而这个我们很容易实现 级别的时间复杂度，所以，记录 和 分别表示上个状态转以后已经处理完的左右端点，如果两状态位于分治中同一区间，则每次转移需要 的时间复杂度，如果改变了区间，需要先跳到所求区间，设两区间分别为 和 所需要跳的步数即为 ，放在分治中即可粗略计算为每层跳 次，每次跳跃转移点同样需要 ，综上所述，时间复杂度为 可以通过该题。

求顺序对时若使用线段树实现，时间超限，得分60pts，使用常数更小的树状数组实现，成功通过该题。

另外，观察状态转移方程，每次转移只和 有关，所以我们可以压缩掉一维，只记录当前与上一行状态。

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int M=25010; int n,m; int a[M],w[M]; int dp[M][2],tl=1,tr=0,sum=0; int lowbit(int x) { return x&-x; } void add(int x,int w) { for(;x<=n;x+=lowbit(x)) a[x]+=w; } int query(int x) { int ans=0; for(;x;x-=lowbit(x)) ans+=a[x]; return ans; } void ask(int le,int re) { while(tr<re) { ++tr; sum+=query(w[tr]); add(w[tr],1); } while(tl>le) { --tl; sum+=tr-tl-query(w[tl]); add(w[tl],1); } while(tr>re) { add(w[tr],-1); sum-=query(w[tr]); tr--; } while(tl<le) { add(w[tl],-1); sum-=tr-tl-query(w[tl]); tl++; } } void solve(int le,int re,int lt,int rt) { int mid=(le+re)>>1; int k=mid; for(int i=lt;i<=min(rt,mid-1);i++) { ask(i+1,mid); if(dp[i][1]+sum<=dp[mid][0]) { dp[mid][0]=dp[i][1]+sum; k=i; } } if(mid-1>=le) solve(le,mid-1,lt,k); if(mid+1<=re) solve(mid+1,re,k,rt); } int main() { memset(dp,0x3f,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } dp[0][0]=dp[0][1]=0;