网站建设 维护 编程,装修设计软件app排行榜前5名,做个网站怎么做,wordpress付费主题下载P3195 [HNOI2008]玩具装箱
题意#xff1a;
n件玩具#xff0c;第i件玩具经过压缩后的一维长度为CiC_iCi,现在把玩具装入一维容器中#xff0c;要求#xff1a;
在一个一维容器中的玩具编号是连续的如果一个一维容器中有多个玩具#xff0c;那么两件玩具之间要加入一…P3195 [HNOI2008]玩具装箱
题意
n件玩具第i件玩具经过压缩后的一维长度为CiC_iCi,现在把玩具装入一维容器中要求
在一个一维容器中的玩具编号是连续的如果一个一维容器中有多个玩具那么两件玩具之间要加入一个单位长度的填充物。
制作容器的费用与容器的长度有关。如果容器长度为x其制作费用为(x−L)2(x-L)^2(x−L)2. 问所有容器的总费用最小是多少
题解
斜率优化dp入门题 前置知识 需要会单调队列优化
当dp方程为dp[i]a[i]b[i]时这个方程是O(n2)O(n^2)O(n2)的 此时可以用单调队列将其优化为O(n) 当dp方程为dp[i]a[i]*b[j]c[i]d[j]时因为存在a[i]*b[j]这个即有i又有j的项此时单调队列不好用就需要使用斜率优化
回到本题 这个题的转移方程很好写 sum[i]表示前i件玩具的长度和 dp[i]表示把前i件玩具装进容器所需要的最小费用 dp[i]min(dp[j]((sum[i]−sum[j])(i−j−1)−L)2)(ji)dp[i]min(dp[j]((sum[i]-sum[j])(i-j-1)-L)^2)(ji)dp[i]min(dp[j]((sum[i]−sum[j])(i−j−1)−L)2)(ji) 不过转移显然是O(n2)O(n^2)O(n2)的因此需要进行优化 我们设a[i]sum[i]i,b[j]sum[j]jL1(就是将i和j的式子分开,a只与i有关b只与j有关) 则dp[i]dp[j](a[i]−b[j])2dp[i]dp[j](a[i]-b[j])^2dp[i]dp[j](a[i]−b[j])2 展开有 dp[i]dp[j]a[i]2−2∗a[i]∗b[j]b[j]2dp[i]dp[j]a[i]^2-2*a[i]*b[j]b[j]^2dp[i]dp[j]a[i]2−2∗a[i]∗b[j]b[j]2 移项有 dp[j]b[j]22∗a[i]∗b[j]dp[i]−a[i]2dp[j]b[j]^22*a[i]*b[j]dp[i]-a[i]^2dp[j]b[j]22∗a[i]∗b[j]dp[i]−a[i]2 a[i]sum[i]i,而sum是可以算出来的也就是说a[]是可以预处理出来的我们可以当作是常数 那么这个式子我们就可以认为 是一条斜率为2∗a[i]2*a[i]2∗a[i]的直线解决为dp[i]−a[i]2dp[i]-a[i]^2dp[i]−a[i]2 此时dp[i]的含义就是当上述直线过点(b[j],dp[j]b[j]2)(b[j],dp[j]b[j]^2)(b[j],dp[j]b[j]2)时直线在y轴的截距为dp[i]a[i]2dp[i]a[i]^2dp[i]a[i]2 现在我们要求的就是这个截距的最小值 直线的斜率为2∗a[i]2*a[i]2∗a[i]是递增的由此可以联想到凸包凸包中相邻两点的斜率是单调递增的 由下面的图像可知满足条件的最优的点PjP_jPj为第一个slope(Pj,Pj1)2∗a[i]slope(P_j,P_{j1})2*a[i]slope(Pj,Pj1)2∗a[i]的点 slope表示斜率 再看这个图如果维护凸包一定时弹掉B为什么如果一条直线斜率大于GC的直线从下面平移上来一定会到C这里停下。如果是一条斜率小于GC大于FG的显然会在G停下来B注定要被舍弃这就是为什么要维护凸包。
因此我们用单调队列来优化这个凸包
设队首为head队尾为tail:
对队首 while(slope(Phead,Phead1)2∗a[i])headwhile(slope(P_{head},P_{head1})2*a[i])~~headwhile(slope(Phead,Phead1)2∗a[i]) head 当斜率小于2a[i]时弹出队首此时队首的点即为最优根据它计算出dp[i]对队尾 while(slope(Ptail−1,Ptail)slope(Ptail,Pi))tail−−while(slope(P_{tail-1},P_{tail})slope(P_{tail},P_i))~~tail--while(slope(Ptail−1,Ptail)slope(Ptail,Pi)) tail−−在队尾插入PiP_iPi
初始化时要加入单调队列的点为P0而不是P1初始化时要加入单调队列的点为P_0而不是P_1初始化时要加入单调队列的点为P0而不是P1 在这里我们总结一下,单调队列斜率优化的步骤: 1.弹队头,就是最左边的点. 2.放直线,算答案,得到当前状态的答案,得到新的待加入的点. 3.弹队尾,把插入新点之后不合法的点弹掉.最后加入新点就好了.
代码:
#include cmath
#include cstdio
#include iostream
#define maxn 50005
#define ll long long
using namespace std;
int q[maxn];
double A[maxn], B[maxn], dp[maxn], sum[maxn];
double X(int x)
{return B[x];
}
double Y(int x)
{return dp[x] B[x] * B[x];
}
double slope(int a, int b)
{return (Y(a) - Y(b)) / (X(a) - X(b));
}
int main()
{int n, l;cin n l;for (int i 1; i n; i)scanf(%lf, sum[i]);for (int i 1; i n; i) {sum[i] sum[i - 1];A[i] sum[i] i;B[i] sum[i] i l 1;}B[0] l 1; //B[0]sum[0]0l1l1int tail 1, head 1;for (int i 1; i n; i) {while (head tail slope(q[head], q[head 1]) 2 * A[i]) //如果队首不符合要求弹出head;int j q[head];dp[i] dp[j] (A[i] - B[j]) * (A[i] - B[j]); //进行状态转移//舍去不合格点加入新点while (head tail slope(i, q[tail - 1]) slope(q[tail - 1], q[tail]))tail--;q[tail] i;}printf(%lld, (ll)dp[n]);return 0;
}
