【题目链接】ybt 1613打印文章【题目考点】1. 斜率优化动规斜率优化动规相关知识见信息学奥赛一本通 1607【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2【解题思路】每个单词可以当做一个整数这是个整数序列。c i c_ici为第i ii个整数设c cc序列的前缀和s sss i s_isi表示前i ii个整数的加和。m mm为题目中的M MM。1. 状态定义阶段前i ii个数决策一个数属于哪个子段策略子段划分的方案策略集合前i ii个数的所有子段划分方案条件代价最小统计量代价状态定义d p i dp_idpi前i ii个数的所有子段划分方案中代价最小的方案的代价。初始状态d p 0 0 dp_00dp002. 状态转移方程策略集合前i ii个数的所有子段划分方案分割策略集合根据分出的最后一个子段的长度分割策略集合设最后一个子段为区间[ j 1 , i ] [j1,i][j1,i]j jj最小可以为0最大为i − 1 i-1i−1所以0 ≤ j ≤ i − 1 0\le j \le i-10≤j≤i−1。该子段的代价为( ∑ x j 1 i c x ) 2 m ( s i − s j ) 2 m (\sum\limits_{xj1}^ic_x)^2m(s_i-s_j)^2m(xj1∑icx)2m(si−sj)2m前i ii个数进行子段划分的最小代价为前j jj个数进行子段划分的最小代价再加上子段[ j 1 , i ] [j1,i][j1,i]的代价为d p j ( s i − s j ) 2 m dp_j(s_i-s_j)^2mdpj(si−sj)2m对所有可能的j jj的取值取该表达式的最小值。因此状态转移方程为d p i min { d p j ( s i − s j ) 2 m } 0 ≤ j ≤ i − 1 dp_i\min\{dp_j(s_i-s_j)^2m\}0\le j\le i-1dpimin{dpj(si−sj)2m}0≤j≤i−1。该状态转移方程可以使用斜率优化动规。去掉min将与j jj相关的量当做变量整理方程d p i d p j ( s i − s j ) 2 m d p j s i 2 − 2 s i s j s j 2 m dp_i dp_j(s_i-s_j)^2mdp_js_i^2-2s_is_js_j^2mdpidpj(si−sj)2mdpjsi2−2sisjsj2md p j s j 2 2 s i s j d p i − s i 2 − m dp_js_j^22s_is_jdp_i-s_i^2-mdpjsj22sisjdpi−si2−m设y d p j s j 2 , x s j , k 2 s i , b d p i − s i 2 − m ydp_js_j^2, x s_j, k 2s_i, b dp_i-s_i^2-mydpjsj2,xsj,k2si,bdpi−si2−m则该方程就是直线方程y k x b ykxbykxb决策点为( s j , d p j s j 2 ) (s_j, dp_js_j^2)(sj,dpjsj2)看直线经过哪个决策点时截距b bb最小将决策点的值带入即可求出d p i dp_idpi。已知c i c_ici是非负的所以随着i ii的增大s i s_isi增大斜率k kk随之增大。可以进行队头出队操作取队头即为最优决策点。最终结果为d p n dp_ndpn【题解代码】解法1斜率优化动规//j1~i为最后一段//dp[i] min{dp[j](s[i]-s[j])^2M} 0ji-1#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN500005;LL n,m,a[N],s[N],dp[N];//dp[i]前i个数的所有划分中代价最小的划分方案的代价intq[N],l,r;LLX(intj){returns[j];}LLY(intj){returndp[j]s[j]*s[j];}LLK(inti){return2*s[i];}boolcmp(LL a1,LL b1,LL a2,LL b2)//a1/b1 a2/b2{returna1*b2a2*b1;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);while(cinnm){l1,r0;//单调队列清空for(inti1;in;i){cina[i];s[i]s[i-1]a[i];}q[r]0;for(inti1;in;i){while(lrcmp(Y(i-1)-Y(q[r]),X(i-1)-X(q[r]),Y(q[r])-Y(q[r-1]),X(q[r])-X(q[r-1])))--r;q[r]i-1;while(lrcmp(Y(q[l1])-Y(q[l]),X(q[l1])-X(q[l]),K(i),1))l;dp[i]dp[q[l]](s[i]-s[q[l]])*(s[i]-s[q[l]])m;}coutdp[n]\n;}return0;}
信息学奥赛一本通 1613：打印文章
发布时间：2026/7/28 7:52:20
【题目链接】ybt 1613打印文章【题目考点】1. 斜率优化动规斜率优化动规相关知识见信息学奥赛一本通 1607【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2【解题思路】每个单词可以当做一个整数这是个整数序列。c i c_ici为第i ii个整数设c cc序列的前缀和s sss i s_isi表示前i ii个整数的加和。m mm为题目中的M MM。1. 状态定义阶段前i ii个数决策一个数属于哪个子段策略子段划分的方案策略集合前i ii个数的所有子段划分方案条件代价最小统计量代价状态定义d p i dp_idpi前i ii个数的所有子段划分方案中代价最小的方案的代价。初始状态d p 0 0 dp_00dp002. 状态转移方程策略集合前i ii个数的所有子段划分方案分割策略集合根据分出的最后一个子段的长度分割策略集合设最后一个子段为区间[ j 1 , i ] [j1,i][j1,i]j jj最小可以为0最大为i − 1 i-1i−1所以0 ≤ j ≤ i − 1 0\le j \le i-10≤j≤i−1。该子段的代价为( ∑ x j 1 i c x ) 2 m ( s i − s j ) 2 m (\sum\limits_{xj1}^ic_x)^2m(s_i-s_j)^2m(xj1∑icx)2m(si−sj)2m前i ii个数进行子段划分的最小代价为前j jj个数进行子段划分的最小代价再加上子段[ j 1 , i ] [j1,i][j1,i]的代价为d p j ( s i − s j ) 2 m dp_j(s_i-s_j)^2mdpj(si−sj)2m对所有可能的j jj的取值取该表达式的最小值。因此状态转移方程为d p i min { d p j ( s i − s j ) 2 m } 0 ≤ j ≤ i − 1 dp_i\min\{dp_j(s_i-s_j)^2m\}0\le j\le i-1dpimin{dpj(si−sj)2m}0≤j≤i−1。该状态转移方程可以使用斜率优化动规。去掉min将与j jj相关的量当做变量整理方程d p i d p j ( s i − s j ) 2 m d p j s i 2 − 2 s i s j s j 2 m dp_i dp_j(s_i-s_j)^2mdp_js_i^2-2s_is_js_j^2mdpidpj(si−sj)2mdpjsi2−2sisjsj2md p j s j 2 2 s i s j d p i − s i 2 − m dp_js_j^22s_is_jdp_i-s_i^2-mdpjsj22sisjdpi−si2−m设y d p j s j 2 , x s j , k 2 s i , b d p i − s i 2 − m ydp_js_j^2, x s_j, k 2s_i, b dp_i-s_i^2-mydpjsj2,xsj,k2si,bdpi−si2−m则该方程就是直线方程y k x b ykxbykxb决策点为( s j , d p j s j 2 ) (s_j, dp_js_j^2)(sj,dpjsj2)看直线经过哪个决策点时截距b bb最小将决策点的值带入即可求出d p i dp_idpi。已知c i c_ici是非负的所以随着i ii的增大s i s_isi增大斜率k kk随之增大。可以进行队头出队操作取队头即为最优决策点。最终结果为d p n dp_ndpn【题解代码】解法1斜率优化动规//j1~i为最后一段//dp[i] min{dp[j](s[i]-s[j])^2M} 0ji-1#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN500005;LL n,m,a[N],s[N],dp[N];//dp[i]前i个数的所有划分中代价最小的划分方案的代价intq[N],l,r;LLX(intj){returns[j];}LLY(intj){returndp[j]s[j]*s[j];}LLK(inti){return2*s[i];}boolcmp(LL a1,LL b1,LL a2,LL b2)//a1/b1 a2/b2{returna1*b2a2*b1;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);while(cinnm){l1,r0;//单调队列清空for(inti1;in;i){cina[i];s[i]s[i-1]a[i];}q[r]0;for(inti1;in;i){while(lrcmp(Y(i-1)-Y(q[r]),X(i-1)-X(q[r]),Y(q[r])-Y(q[r-1]),X(q[r])-X(q[r-1])))--r;q[r]i-1;while(lrcmp(Y(q[l1])-Y(q[l]),X(q[l1])-X(q[l]),K(i),1))l;dp[i]dp[q[l]](s[i]-s[q[l]])*(s[i]-s[q[l]])m;}coutdp[n]\n;}return0;}
