2020-2021:teams:legal_string:jxm2001:动态规划_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:动态规划_2 [2020/10/31 19:58] jxm2001 [习题一] |
2020-2021:teams:legal_string:jxm2001:动态规划_2 [2021/02/11 18:58] (当前版本) jxm2001 [习题一] |
||
|---|---|---|---|
| 行 223: | 行 223: | ||
| === 题意 === | === 题意 === | ||
| - | 给定序列 $c$ 和常数 $L$。已知一个区间 $[l,r]$ 的权值为 $(\sum_{i=l}^r c_i+r-l+1-L)^2$。现要求将 $[1,n]$ 划分为若干连续区间，使得权值和最小。 | + | 给定序列 $c$ 和常数 $L$。已知一个区间 $[l,r]$ 的权值为 $(\sum_{i=l}^r c_i+r-l-1-L)^2$。现要求将 $[1,n]$ 划分为若干连续区间，使得权值和最小。 |
| === 题解 === | === 题解 === | ||
| 行 230: | 行 230: | ||
| $$ | $$ | ||
| - | \text{dp}_i=\max(dp_j+(s_i+i-s_j-j-L-1)^2) | + | \text{dp}_i=\min(dp_j+(s_i+i-s_j-j-L-1)^2) |
| $$ | $$ | ||
| 行 236: | 行 236: | ||
| $$ | $$ | ||
| - | \text{dp}_i=\text{dp}_j+(a_i-b_j)^2=a_i^2+\text{dp}_j+b_j^2+2a_ib_j | + | \text{dp}_i=\text{dp}_j+(a_i-b_j)^2=a_i^2+\text{dp}_j+b_j^2-2a_ib_j |
| $$ | $$ | ||
| 行 242: | 行 242: | ||
| $$ | $$ | ||
| - | \text{dp}_i-a_i^2=y=a_ix | + | \text{dp}_i-a_i^2=y-a_ix |
| $$ | $$ | ||
| - | 于是维护凸包即可，另外发现 $a_i$ 和 $x$ 递增，于是可以单调队列维护凸包，时间复杂度 $O(n)$。 | + | 于是维护凸包即可，另外发现 $a_i$ 和 $x$ 递增，于是可以单调队列维护凸包，时间复杂度 $O(n)$。注意最开始需加入 $(a_0,b_0)$。 |
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 273: | 行 273: | ||
| return 0; | return 0; | ||
| } | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | ==== 习题二 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4072|洛谷p4072]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定 $n$ 个数，定义一个区间的权值为该区间所有数的权值和。现要求将其划分为 $m$ 个区间，使得区间权值的方差最小。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 考虑方差等于平方的平均值减去平均值的平方。平均值的平方为定值，现在考虑最小化平方和。 | ||
| + | |||
| + | 设 $\text{dp}(k,i)$ 表示将前 $i$ 个数划分为 $k$ 个区间的答案，于是有状态转移方程 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(k,i)=\min(\text{dp}(k-1,j)+(s_i-s_j)^2) | ||
| + | $$ | ||
| + | |||
| + | 移项得 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(k,i)-s_i^2=\text{dp}(k-1,j)+s_j^2-2s_is_j | ||
| + | $$ | ||
| + | |||
| + | 令 $x=2s_j,y=\text{dp}(k-1,j)+s_j^2$，暴力 $m$ 次斜率优化即可，时间复杂度 $O(nm)$。注意边界条件为 $\text{dp}(1,i)=s_i^2$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e4+5; | ||
| + | int dp[2][MAXN],s[MAXN],q[MAXN],pos; | ||
| + | double slope(int i,int j){return (double)(dp[!pos][i]+s[i]*s[i]-dp[!pos][j]-s[j]*s[j])/(2*s[i]-2*s[j]);} | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | pos=0; | ||
| + | _rep(i,1,n) | ||
| + | s[i]=s[i-1]+read_int(),dp[pos][i]=s[i]*s[i]; | ||
| + | _for(k,1,m){ | ||
| + | pos=!pos; | ||
| + | int head=0,tail=-1; | ||
| + | q[++tail]=0; | ||
| + | _rep(i,1,n){ | ||
| + | while(head<tail&&slope(q[head],q[head+1])<s[i])head++; | ||
| + | dp[pos][i]=dp[!pos][q[head]]+(s[i]-s[q[head]])*(s[i]-s[q[head]]); | ||
| + | while(head<tail&&slope(q[tail],i)<slope(q[tail-1],q[tail]))tail--; | ||
| + | q[++tail]=i; | ||
| + | } | ||
| + | } | ||
| + | enter(m*dp[pos][n]-s[n]*s[n]); | ||
| + | return 0; | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ==== 习题三 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/CF311B|CF311B]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一条链，链上有 $n$ 个点，编号相邻两点距离为 $D_i$。接下来给定 $m$ 只猫，每只猫位于 $H_i$ 号点，且在第 $T_i$ 秒开始等待。 | ||
| + | |||
| + | 接下来有 $p$ 个人，每个人速度为 $1$ 且可以从任意时刻出发且从 $1$ 号点不停止地走到 $n$ 号点并带走所有已经开始等待的猫。 | ||
| + | |||
| + | 问所有猫等待时间的最小可能值。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 对每条猫，计算出使得它等待时间为 $0$ 的出发时间 $t_i$，将 $t_i$ 从小到大排序。 | ||
| + | |||
| + | 将序列 $t$ 划分为 $p$ 个区间，每个区间派一个人，显然这个人必须在该区间 $t$ 的最大值的时刻出发。 | ||
| + | |||
| + | 设 $\text{dp}(i,j)$ 表示派 $i$ 个人接前 $j$ 只猫需要花费的最小时间，$s_n=\sum t_i$，于是有状态转移方程 | ||
| + | |||
| + | $$ | ||
| + | \text{dp}(i,j)=\min_{k\lt j}\left(\text{dp(i-1,k)}+\sum_{x=k+1}^j (t_j-t_x)\right)=\min_{k\lt j}\left(\text{dp(i-1,k)}+(j-k)t_j+s_j-s_k\right)=\min_{k\lt j}\left(\text{dp(i-1,k)}-s_k-t_jk\right)+jt_j+s_j | ||
| + | $$ | ||
| + | |||
| + | 时间复杂度 $O(mp)$。 | ||
2020-2021/teams/legal_string/jxm2001/动态规划_2.1604145511.txt.gz · 最后更改: 2020/10/31 19:58 由 jxm2001
