2020-2021:teams:legal_string:jxm2001:wqs二分
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/16 09:39] jxm2001 [例题三] |
2020-2021:teams:legal_string:jxm2001:wqs二分 [2021/08/24 17:22] (当前版本) jxm2001 [例题四] |
||
|---|---|---|---|
| 行 221: | 行 221: | ||
| 不难发现对固定的 $x$，$F(x,y)$ 是凸函数，于是利用 $\text{wqs}$ 二分可以 $O(n\log v)$ 计算出 $F(x,b)$。 | 不难发现对固定的 $x$，$F(x,y)$ 是凸函数，于是利用 $\text{wqs}$ 二分可以 $O(n\log v)$ 计算出 $F(x,b)$。 | ||
| - | 然后显然 $F(x,b)$ 也是凸函数，于是再套一层 $\text{wqs}$ 二分可以 $O(n\log^2 v)$ 计算出 $F(a,b)$。 | + | 然后显然 $F(x,b)$ 也是凸函数，于是再套一层 $\text{wqs}$ 二分可以 $O\left(n\log^2 v\right)$ 计算出 $F(a,b)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 283: | 行 283: | ||
| } | } | ||
| printf("%.6lf",solve(lef).s+lef*a); | printf("%.6lf",solve(lef).s+lef*a); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 例题四 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4983|洛谷p4983]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定序列 $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; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/wqs二分.1629077951.txt.gz · 最后更改: 2021/08/16 09:39 由 jxm2001
