思路首先我们很好得出这种分段问题的状态转移方程即其中 表示选到前 个数分了 段的最小费用我们可以用 的时间复杂度来实现显然超时得分20pts。接着考虑优化不难发现所以该式子满足四边形不等式即可使用决策单调性来优化该状态转移方程。P4767邮局这道题与该题状态转移方程相同所以一上手想到使用四边形不等式中 的性质优化该题优化该题然而这种算法时间复杂度为 并不能通过该题结果超时得分40pts邮局一题中 与 上界相同而该题 远小于 我们需要使用分治优化将时间复杂度降到 级别才能通过。我们解决了DP阶段的问题接着需要解决的就是预处理 数组的问题了由于我们无法接受 的时间复杂度所以我们要对其进行优化因为数组大小的限制预处理出 数组这条思路已经行不通了我们考虑在DP过程中求一段的花费注意到在分治求解的过程中当决策点每向右移动一位我们的费用由 变为 过程中我们增加的顺序对费用即为 到 中小于 的数的个数而这个我们很容易实现 级别的时间复杂度所以记录 和 分别表示上个状态转以后已经处理完的左右端点如果两状态位于分治中同一区间则每次转移需要 的时间复杂度如果改变了区间需要先跳到所求区间设两区间分别为 和 所需要跳的步数即为 放在分治中即可粗略计算为每层跳 次每次跳跃转移点同样需要 综上所述时间复杂度为 可以通过该题。求顺序对时若使用线段树实现时间超限得分60pts使用常数更小的树状数组实现成功通过该题。另外观察状态转移方程每次转移只和 有关所以我们可以压缩掉一维只记录当前与上一行状态。代码#includebits/stdc.h #define ll long long using namespace std; const int M25010; int n,m; int a[M],w[M]; int dp[M][2],tl1,tr0,sum0; int lowbit(int x) { return x-x; } void add(int x,int w) { for(;xn;xlowbit(x)) a[x]w; } int query(int x) { int ans0; for(;x;x-lowbit(x)) ansa[x]; return ans; } void ask(int le,int re) { while(trre) { tr; sumquery(w[tr]); add(w[tr],1); } while(tlle) { --tl; sumtr-tl-query(w[tl]); add(w[tl],1); } while(trre) { add(w[tr],-1); sum-query(w[tr]); tr--; } while(tlle) { add(w[tl],-1); sum-tr-tl-query(w[tl]); tl; } } void solve(int le,int re,int lt,int rt) { int mid(lere)1; int kmid; for(int ilt;imin(rt,mid-1);i) { ask(i1,mid); if(dp[i][1]sumdp[mid][0]) { dp[mid][0]dp[i][1]sum; ki; } } if(mid-1le) solve(le,mid-1,lt,k); if(mid1re) solve(mid1,re,k,rt); } int main() { memset(dp,0x3f,sizeof(dp)); scanf(%d%d,n,m); for(int i1;in;i) { scanf(%d,w[i]); } dp[0][0]dp[0][1]0;