P5574 [CmdOI2019] 任务分配问题

📅 2026/7/2 1:49:00 👁️ 次浏览

思路首先我们很好得出这种分段问题的状态转移方程即其中表示选到前个数分了段的最小费用我们可以用的时间复杂度来实现显然超时得分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;

相关新闻