`
feiliboos
  • 浏览: 659602 次
文章分类
社区版块
存档分类
最新评论

[APIO2010]特别行动队

 
阅读更多

很显然是个DP

有方程f[i]=max{f[j]+Ax^2+Bx+C} x=s[i]-s[j] j∈[1,i-1]

这样一个DP方程是O(n^2)的,对于原题最多只能过50%数据


那么这道题可以斜率优化

从方程着手,方程可以化为

f[i]=max{(f[j]+A*s[j]^2+B*s[j]+C)+(-2A*s[i]*s[j])}+A*s[i]^2+A*s[i]

我们把(f[j]+A*s[j]^2+B*s[j]+C)看成y,(-2A*s[i]*s[j])看成-kx,-s[i]是斜率,递减,-2A*s[j]是x,递增

那么每个决策对应平面上一个点

而且斜率和横坐标均单调,可以用单调队列维护

对于每个i

弹出单调队列队首直到单调队列队首最优,

计算f[i]

在单调队列中维护相邻两个决策点的斜率单调递减

push决策点i



代码写得比较丑……



分享到:
评论

相关推荐

    APIO2021.zip

    APIO2021课件

    APIO2012 中文版

    CCF全国青少年信息学奥赛 APIO 亚洲与太平洋地区信息学奥林匹克 2012年 试题 中文版

    APIO2008.pdf

    APIO2008 亚太地区信息学奥林匹克竞赛

    APIO ATM 测试数据

    apio(亚洲与太平洋地区信息学奥林匹克(Asia-Pacific Informatics Olympiad, APIO),是一个面向亚太地区在校中学生的信息学科竞赛。) 2010 年的测试数据 atm一题 供下载测试用

    APIO2016课件

    APIO2016课件,包含有位运算最小生成树以及组合数取模

    APIO2009试题-中文版

    2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版

    apio2009_convention试题分析

    apio2009 convention 试题分析

    APIO2015.zip

    APIO2015 数据 题面自己搜,1.巴厘岛的雕塑 N个数,分成连续的A-B个组,让每个组的和或起来最小,求最小值。 对于Task1 n  由于涉及到位运算,所以很容易想到按二进制位来做。要让答案最小,显然要从二进制高位...

    APIO2007试题-中文版

    2007年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版

    APIO2012_網絡流題選講

    APIO2012_網絡流題選講。 网络流题选讲 清华大学 计03 李宇亮

    APIO2015年竞赛试题中文版

    2015年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版

    APIO2018资料

    APIO2018的题面与部分课件与pdf和ppt,.在此分享一下。

    APIO2018T1 New Home 题解 吕欣

    题目大意 在一个数轴上: 给定 N 个商店,每个商店有一个开业时间、关门时间、坐标和销售物品的种类 同时有 M 个询问,每个询问给你一个时间 t[i] 和地点 d[i],试求在 t[i] 时刻,一个住在 d[i] 的人,为了买某种...

    APIO2014课件

    讲题: beads.pdf palindrome-pres.pdf sequence.pdf 课件: 冯齐纬 彭天翼 毕克 罗雨屏 胡渊鸣 陈立杰

    APIO2013课件

    1钱桥_提交答案题目的处理方法.pptx 2冯齐纬_URAL题目选讲 3曹钦翔_线段树应用.pptx 4李超_Problems in UralChampionship.pptx 5陈许旻_数论与AI

    APIO2014年竞赛试题测试数据

    2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题测试数据

    APIO2015 Problemset

    APIO2015的problemset, 非常的清楚.

    apio:用于开放FPGA板的开源生态系统

    用于开放FPGA板的开源生态系统Apio(发音为[ˈa.pjo])是一个多平台工具箱,具有静态的预构建软件包,项目配置工具和简单的命令界面,可用于验证,综合,模拟和上传Verilog设计。 Icestudio使用 。目录安装安装和 ...

    APIO2008试题-中文版

    2008年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版

    APIO2014年竞赛试题中文版

    2014年亚太地区信息学奥林匹克竞赛(Asia-Pacific Informatics Olympiad, APIO)试题中文版

Global site tag (gtag.js) - Google Analytics