2020-2021:teams:legal_string:jxm2001:wqs二分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/24 17:15] jxm2001 |
2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/24 17:22] (当前版本) jxm2001 [例题四] |
||
|---|---|---|---|
| 行 294: | 行 294: | ||
| === 题意 === | === 题意 === | ||
| - | 给定序列 $A$ | + | 给定序列 $A$，定义子串 $A[l\sim r]$ 的费用为 $(\sum_{i=l}^r a_i+1)^2$。要求将 $A$ 划分成 $m$ 段，最小化费用。 |
| === 题解 === | === 题解 === | ||
| + | |||
| + | $\text{wqs}$ 二分套斜率优化，斜率优化的难点在于 $\text{wqs}$ 二分具有第二关键字，即收益相同的情况下需要最大或最小化划分的次数。 | ||
| + | |||
| + | 斜率优化比较难处理这方面的要求。本人的斜率优化板子貌似是强制取最小的，如果 $\text{WA}$ 了可以考虑假设强制取最小的/最大都试试。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | const LL inf=1e18; | ||
| + | int s[MAXN],cnt[MAXN],q[MAXN]; | ||
| + | LL dp[MAXN]; | ||
| + | LL caly(int pos){ | ||
| + | return 1LL*s[pos]*(s[pos]-2)+dp[pos]; | ||
| + | } | ||
| + | double slope(int i,int j){ | ||
| + | return 1.0*(caly(i)-caly(j))/(s[i]-s[j]); | ||
| + | } | ||
| + | pair<LL,int> solve(int n,LL k){ | ||
| + | int head=0,tail=-1; | ||
| + | q[++tail]=0; | ||
| + | _rep(i,1,n){ | ||
| + | while(head<tail&&slope(q[head],q[head+1])<2*s[i])head++; | ||
| + | dp[i]=dp[q[head]]+1LL*(s[i]-s[q[head]]+1)*(s[i]-s[q[head]]+1)-k; | ||
| + | cnt[i]=cnt[q[head]]+1; | ||
| + | while(head<tail&&slope(q[tail],i)<slope(q[tail-1],q[tail]))tail--; | ||
| + | q[++tail]=i; | ||
| + | } | ||
| + | return make_pair(dp[n],cnt[n]); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,n) | ||
| + | s[i]=read_int()+s[i-1]; | ||
| + | LL lef=-inf,rig=0,ans; | ||
| + | while(lef<=rig){ | ||
| + | LL mid=lef+rig>>1; | ||
| + | if(solve(n,mid).second<=m){ | ||
| + | ans=mid; | ||
| + | lef=mid+1; | ||
| + | } | ||
| + | else | ||
| + | rig=mid-1; | ||
| + | } | ||
| + | enter(solve(n,ans).first+1LL*ans*m); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/wqs二分.1629796547.txt.gz · 最后更改: 2021/08/24 17:15 由 jxm2001
