用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:动态规划_2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:jxm2001:动态规划_2 [2020/10/31 22:17]
jxm2001 [习题一]
2020-2021:teams:legal_string:jxm2001:动态规划_2 [2021/02/11 18:58] (当前版本)
jxm2001 [习题一]
行 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
 $$ $$
  
行 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.1604153857.txt.gz · 最后更改: 2020/10/31 22:17 由 jxm2001