HDU 4258 Covered Walkway（斜率优化DP）_Lanifer的博客-程序员秘密

和POJ 3709 K-Anonymous Sequence是完全类似的题目，只是状态方程变了而已。

dp[ i ] = min { dp[ j ] + (A[ i ] - A[ j + 1])*(A[ i ] - A[ j+1 ] ) + C | j<i }

单调队列维护下凸曲线。

记Y[ i ] = dp[ i ] + A[ i+1 ] *A[ i+1 ] , X[ i ] = A[ i+1 ]

rate( a, b) = (Y[b] - Y[a]) / (X[b] - X[a] )

"a<b && b不差于a" 即 " dp[ a ] + (A[ i ] - A[a+1])*(A[ i ] - A[a+1]) + C >= dp[ b ] + (A[ i ] - A[b+1])*(A[ i ] - A[b+1]) + C " 整理得 "rate(a,b) <= 2*A[ i ] "

故有：

① “a<b && b不差于a” 的等价条件是： rate(a , b ) <= 2*A[ i ]

② 最优决策点myque[p]具有性质： rate(myque[p-1] , myque[p] ) <= 2*A[ i ] < rate(myque[p] , myque[p+1] )

利用①筛选队首元素。利用②筛选队尾元素 , 其原理是若rate(a,b)>=rate(b,c) 则rate(a,b) <= 2*A[ i ] < rate(b,c) 恒不成立，即b不可能最优。

代码：

#include <cstdio>
using namespace std;
const int maxn=1000050;
typedef long long LL;
LL A[maxn] ,dp[maxn] , C;
int myque[maxn] , head ,tail;
int N ;
#define Y(i) (dp[i]+A[i+1]*A[i+1])
#define X(i) (A[i+1])
bool head_check(int a,int b,int i){
    return Y(b)-Y(a) <= 2*A[i]*(X(b)-X(a));
}
bool tail_check(int a,int b,int c){
    return (Y(b)-Y(a))*(X(c)-X(b)) >= (Y(c)-Y(b))*(X(b)-X(a));
}
LL F(int j,int i){
    return dp[j] + (A[i]-A[j+1])*(A[i]-A[j+1]) + C ;
}
int main()
{
    while(scanf("%d%I64d",&N,&C)!=EOF && N+C){
        for(int i=1;i<=N;i++) scanf("%I64d",&A[i]);
        dp[0] = 0 ,myque[0] = 0 ,head = tail =0;
        for(int i=1;i<=N;i++){
            while(head < tail && head_check(myque[head],myque[head+1],i)) head++;
            dp[i] = F(myque[head],i);
            while(head < tail && tail_check(myque[tail-1],myque[tail],i)) tail--;
            myque[++tail] = i;
        }
        printf("%I64d\n",dp[N]);
    }
    return 0;
}

本文链接：https://blog.csdn.net/u011276914/article/details/15494231

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

裁纸奔月python_中国大学MOOC的APP2020Python编程基础期末考试搜题公众号答案_weixin_39836860的博客-程序员秘密

中国大学MOOC的APP2020Python编程基础期末考试搜题公众号答案更多相关问题【判断题】高级训练者的大肌肉群练习一般不超过10-12组。A. 对B. 错When customers receive the goods _____ quality, they may make a complaint or file a claim against the supplier.【单选题】信用卡有...

简单说一下业务接口自动化测试_业务不固化,改动频繁能做接口自动化测试吗_Sam_Deep_Thinking的博客-程序员秘密

概述在创业公司里，项目都比较赶，测试人员也是疲于测试功能模块，基本没空去写什么自动化测试，以提升回归测试的效率。但一个必须承认的事实便是，依赖测试人员去做全面回归测试，保证质量，是不可取的，因为难度太大，成本太高。因此自动化测试还是要做一些的，具体如何着手呢，下文说一下我这边的做法。注意:本文主要描述一下业务接口自动化测试的方案，至于GUI自动化测试和压力自动化测试不在本文的讨论范围内。...

一篇文章教你在三维空间中创建流动线条(three.js实战1)_threejs 流动线_点燃火柴的博客-程序员秘密

一文教你在三维视图中创建流动线条1.demo效果2. 流动线条实现思路3. 实现要点3.1 定义线条运动轨迹3.2 绘制流动线所需的其他参数3.3 初始化线条3.4 线条流动实现3.5 环形线条函数封装3.6 流动线条函数使用4. demo代码4.1 HTML文件4.2 JS文件1.demo效果2. 流动线条实现思路首先定义一条线段流动的的轨迹线，从这条线上均匀的取若干个点，从这些轨迹点中的某一点开始取若干个点，绘制线条，起始点后移，在取相同的点绘制线条，起始点不断后移，不会绘制线条，就得到流动

springboot-2_springboot学习保鲜盒_保鲜盒的博客-程序员秘密

Spring官方网站本身使用Spring框架开发，随着功能以及业务逻辑的日益复杂，应用伴随着大量的XML配置文件以及复杂的Bean依赖关系。随着Spring 3.0的发布，Spring IO团队逐渐开始摆脱XML配置文件，并且在开发过程中大量使用“约定优先配置”（convention over configuration）的思想来摆脱Spring框架中各类繁复纷杂的配置（即时是Java Con

Python安装数据包_配置python数据包_远见不如短视的博客-程序员秘密

近来对大数据分析有了一定的学习，特做笔记记录，以备回顾，特此mark。语言和Python是大数据分析中常用的两种语言，虽然Java也可进行大数据分析，但R语言和Python浩如烟海的各类数据分析包的支持使得R语言和Python成为了数据分析的主流。 Python在Windows下安装完成，配置好环境变量之后便可以使用命令安装所需要的数据包了，可以说是非常简单的。 1、在...

yolov3 计算coco、voc数据集map_yolov3 voc map__g_y_的博客-程序员秘密

计算voc数据集MAP1、首先下载voc数据集wget https://pjreddie.com/media/files/VOCtrainval_11-May-2012.tarwget https://pjreddie.com/media/files/VOCtrainval_06-Nov-2007.tarwget https://pjreddie.com/media/files/VO...