首页 > 资讯 > 其他 > 正文

斜率优化讲解（例题：Print Article HDU - 3507 斜率优化） - CSDN博客

18-08-07 来源：[db:作者]

收藏我要投稿

斜率优化的学习：

题意：

将序列划分，每段花费如题：区间和平方+m；求最小花费；

思路：

用dp[i] 表示前i个数划分的最优解，sum[i] 表示前i个数的和

显然dp[i] = max ( dp[j] + (sum[i]-sum[j])2 + m ) for j : 0 to i-1;? 复杂度O(n2)：×

即需用到“斜率优化”；

对于一般的n2-dp方程，可能有dp[i] = f[j] + x[i] + k ：?dp[i]为到i的最优解，f[j] 为只包含j的一些已知条件（一般包括dp[j]），x[i] 为只包含x的一些值，k为常数，，我们也可以把 x[i]和k 都看做常数，因为对于某个i，我们寻找j 的时候，这两个都是定值，所以求解的时候只需要维护 f[j] 的最优情况即可；复杂度O(n);? ?(这种情况不是斜率优化，在这里不适用)

斜率优化就是可以转化为斜率关系的dp转移方程，能够将前面一些明显不能帮助后面得到最优情况的点去掉，降低了复杂度；

将dp方程转化为斜率关系需要处理前面多个点的关系；对于本题：

首先化简dp方程：dp[i] = dp[j] + sumi2 + sumj2 -?2*sumi*sumj + m;

对于 k < j < i ；求解dp[i] 时，我们设选择 j 点更新dp[i] 比选择 k 点更优，

那么：?dp[j] + sumj2 -?2*sumi*sumj?

=>? [ (dp[j] + sumj2) -??(dp[k] +?sumk2) ] ÷ [ sumj?- sumk ]?

令 d[j,k] =?[ (dp[j] + sumj2) -??(dp[k] +?sumk2) ] ÷ [ sumj?- sumk ],，可以形式化的表征 k-j 线段的斜率

由上面我们可以得到：对 dp[i] 求解时，若d[j,k] < sumi，那么说明?d[j,k] < sumx （x>=i），即 j点更优，k点可以去掉

然后我们考虑 k < j < i 三点时 d[i,j] ?d[j,k] 三种情况：

<1.>? d[i,j] = sumi，则d[j,k] > sumi, k优，j可以去掉?

<2.>? d[i,j] =?d[j,k] 时：若d[i,j] < sumi ，i优，j可以去掉，若d[i,j] = sumi，j不是唯一最优，可以去掉，若d[i,j] >?sumi，则d[j,k] > sumi, k优，j可以去掉?

<3.>? d[i,j] >?d[j,k] 时：略

综上：d[i,j] <= d[j,k]? 可以去掉 j点，达到优化的目的，用队列维护前面的点

这样在更新dp[i] 时，对于维护的?i 点前的一些点，相邻的三个点 a,b,c 都有d[c,b] > d[b,a] ; 当d[b,a] <= sumi 时，b点更优，a点可以去掉，否则a点即为更新i点的最优点

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 5e5 + 7;
int dp[maxn];
int sum[maxn];
int n, m;
int qu[maxn];
int get1(int i, int j) {
 return (dp[i]+sum[i]*sum[i] - dp[j]-sum[j]*sum[j]);
}
int get2(int i, int j) {
 return 2*(sum[i]-sum[j]);
}
bool is_ok(int k, int j, int i) {
 return (get1(i,j)*get2(j,k) <= get1(j,k)*get2(i,j) );
}
int main() {
 while(scanf("%d%d", &n, &m) == 2) {
  for(int i = 1; i <= n; ++i) {
scanf("%d", &sum[i]);
  }
  qu[0] = sum[0] = dp[0] = 0;
  for(int i = 1; i <= n; ++i) {
sum[i] += sum[i-1];
  }
  int idl = 0, idr = 0;
  for(int i = 1; i <= n; ++i) {
while(idl < idr && get1(qu[idl+1],qu[idl])<=sum[i]*get2(qu[idl+1],qu[idl])) idl++;
int j = qu[idl];
dp[i] = dp[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + m;
while(idr>idl && is_ok(qu[idr-1],qu[idr],i)) idr--;
qu[++idr] = i;
  }
  printf("%d\n", dp[n]);
 }
 return 0;
}

点击复制链接与好友分享!回本站首页

斜率优化讲解 （例题：Print Article HDU - 3507 斜率优化） - CSDN博客

斜率优化讲解（例题：Print Article HDU - 3507 斜率优化） - CSDN博客