斜率优化 - hzwer.com

2016 ACM – ICPC Shenyang Onsite
一些队友写的还没太搞清楚，就先贴几题hdu5948.ThickestBurger模拟[crayon-674027a224de0826873092/]hdu5949.Relativeatomicmass模拟[crayon-674027a224de9919553667/]hdu5950.Recursivesequence\(f_1=a,f_2=b,f_i=f_{i-2}*2+f_{i-1}+i^4\)，求\(f_n\)推出式子后矩阵乘法[crayon-674027a224dee066389755/]hdu5952.CountingCliques求一个无向图大小为S的团的数量由于图的度数很小，选一个点，在其所有相邻点中取S-1个复杂度...
02016年11月8日5,166模拟,深度搜索,斜率优化,矩阵乘法

「BZOJ3675」[Apio2014] 序列分割
Description小H最近迷上了一个分割序列的游戏。在这个游戏里，小H需要将一个长度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列，小H将重复进行七次以下的步骤：1．小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列一一也就是一开始得到的整个序列）；2．选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将会得到一定的分数。这个分数为...
42015年4月19日8,410斜率优化,决策单调性
「火影完结纪念赛」木叶的军师
木叶的军师（nara..pas./c./cpp）时间限制：5s，空间限制：256MB题目背景：奈良鹿丸，拥有出众的应敌策略，头脑冷静、随机应变，IQ超过200。在第四次忍界大战时，父亲奈良鹿久死亡，鹿丸成为木叶乃至忍者联军的新任军师。最后成为了鸣人的左右手，与沙暴手鞠成婚……题目描述：既然是军师，鹿丸就必须要为木叶村的忍者编队。可是，他最怕麻烦了。所以它将这个任务交给了你。木叶村有T个中队，你需要将每个中队的n名忍者分为m个...
02015年1月18日4,264斜率优化
「BZOJ3437」小P的牧场
Description 背景小P是个特么喜欢玩MC的孩纸。。。描述小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需...
22014年11月29日6,606递推与动规,斜率优化
「BZOJ1010」[HNOI2008] 玩具装箱toy
DescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第...
72014年11月28日25,462斜率优化,决策单调性
「BZOJ3156」防御准备
DescriptionInput第一行为一个整数N表示战线的总长度。第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。Output共一个整数，表示最小的战线花费值。SampleInput102315456312SampleOutput18HINT1<=N<=10^6,1<=Ai<=10^9题解裸的斜率优化把a[i]都反过来sum[i]=sum[i-1]+if[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*j}[crayon-674027a227bd4806456102/] ...
02014年6月16日4,359斜率优化
「BZOJ1096」[ZJOI2007] 仓库建设
DescriptionL公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工...
22014年5月18日5,556斜率优化
「BZOJ1911」[Apio2010] 特别行动队commando
DescriptionInputOutputSampleInput4-110-202234SampleOutput9HINT题解我发现似乎掌握了特殊的斜率优化技巧，我会假装四处看风景dp方程：f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)如果j>k且j比k更优f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i][crayon-674027a2286a6419002289/] ...
22014年5月18日6,209斜率优化
「BZOJ1597」[Usaco2008 Mar] 土地购买
Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换.如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25.FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费.他需要你帮助他...
22014年5月18日6,566斜率优化