[SDOI2016] 征途
题目描述
Pine 开始了从 \(S\) 地到 \(T\) 地的征途。
从 \(S\) 地到 \(T\) 地的路可以划分成 \(n\) 段，相邻两段路的分界点设有休息站。
Pine 计划用 \(m\) 天到达 \(T\) 地。除第 \(m\) 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。
设方差是 \(v\)，可以证明，\(v\times m^2\) 是一个整数。为了避免精度误差，输出结果时输出 \(v\times m^2\)。
输入格式
第一行两个数 \(n, m\)。
第二行 \(n\) 个数，表示 \(n\) 段路的长度。
输出格式
一个数，最小方差乘以 \(m^2\) 后的值。
样例 #1
样例输入 #1
5 2
1 2 5 8 6
样例输出 #1
36
提示
数据范围及约定
- 对于 \(30\%\) 的数据，\(1 \le n \le 10\)；
- 对于 \(60\%\) 的数据，\(1 \le n \le 100\)；
- 对于 \(100\%\) 的数据，\(1 \le n \le 3000\)。
保证从 \(S\) 到 \(T\) 的总路程不超过 \(3\times 10^4\)。
从头开始的四边形不等式。。
能让我来编蓝书吗，这一段我感觉我能编的比李煜东好（逃
但是有一说一，我感觉前面的其他部分，蓝书讲的都好的无可挑剔了，但是四边形不等式给我一种摆烂的感觉（而且其实dp决策单调性优化并没有就此结束）
这篇博客帮我再入门了
而蓝书上讲的后面部分的，其实是这篇博客讲的广义决策单调性中的路径交错模型。这个理解起来真的比蓝书上面的抽象证明更加方便，而且，能够清晰的提示出来这个方法的适用范围（我前面几篇博客就被这个适用范围整的死去活来的。。）
哎哎，蓝书也有这么大的缺点啊
这题很明显的满足四边形不等式。
和诗人小G很相似，只不过这题的代价函数能够写开成比较简单的形式，所以能斜率优化，而诗人小G的代价函数嘛。。
为方便书写，下面的代价表示为这一段的方差\(\times m^2\)
状态方程设\(f[i][j]\)表示给前\(i\)个路分为\(j\)段的最小代价
转移方程\(f[i][j]=\displaystyle\min_{1\leq k<i}(f[k][j-1]+val(k,i))\)
其中\(val(k,i)=(\displaystyle\sum_{h=k}^{h\leq i}(x[h])-len/m)^2*m^2\)
\(val(k,i)=(m*\displaystyle\sum_{h=k}^{h\leq i}(x[h])-len)^2\) \(val(k,i)=(\displaystyle\sum_{h=k}^{h\leq i}(x[h])-len/m)^2*m^2\)
\(val(k,i)=(m*(SumX[i]-SumX[k-1])-len)^2\)
拆开二次项，和诗人小G的\(p=2\)的情况一样（但是都是紫题，为什么有的题目会只是其他题目的20分的情况呢？）
\(val(k,i)=((m*SumX[i]-len)-m*SumX[k-1])^2\)
\(val(k,i)=(m*SumX[i]-len)^2-2*(m*SumX[k-1])*(m*SumX[i]-len)+m*SumX[k-1]^2\)
\(val(k,i)=(m*SumX[i]-len)^2-2*(m*SumX[k-1])*(m*SumX[i]-len)+m*SumX[k-1]^2\)
\(=(m*SumX[i]-len)^2-2*(m^2*SumX[k-1]*SumX[i]-len*m*SumX[k-1])+m*SumX[k-1]^2\)
\(=(m*SumX[i]-len)^2-2*m^2*SumX[k-1]*SumX[i]+2*len*m*SumX[k-1]+m*SumX[k-1]^2\)
式子就是这样了，k范围单调向右移动，\(SumX[i]\)斜率单调递增，最简单的形式
不过最近确实好久没写过斜率优化了，写一写吧
我tm的，写完了没保存啊啊啊啊啊啊啊啊啊，然后电脑炸了
上面的思路有问题。。导致写出来的方程极其复杂
破防了
我本来好点的思路的题解都写完了，电脑炸了。。。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我受不了了
我不把式子写一遍，写代码都难受。。
\(f[i][j]+sum[i]^2+2*sum[i]*sum[k]=f[k][j-1]+sum[k]^2\)
\(f[k][j-1]+sum[k]^2=2*sum[i]*sum[k]+f[i][j]-sum[i]^2\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
char c=getchar();int a=0,b=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,m,SumX[3001],f[3001][3001],len;
int q[3001],l,r;
double Y(int k,int j)
{
return f[k][j-1]+SumX[k]*SumX[k];
}
double X(int k)
{
return 2*SumX[k];
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)
{
SumX[i]=SumX[i-1]+read();
f[i][1]=SumX[i]*SumX[i];
}
for(int j=2;j<=m;j++)
{
l=r=1;
q[1]=j-1;
for(int i=j;i<=n;i++)
{
while(l<r&&((Y(q[l],j)-Y(q[l+1],j))>=(X(q[l])-X(q[l+1]))*SumX[i]))l++;
f[i][j]=f[q[l]][j-1]+(SumX[i]-SumX[q[l]])*(SumX[i]-SumX[q[l]]);
while(l<r&&(Y(q[r-1],j)-Y(q[r],j))*(X(q[r])-X(i))>(Y(q[r],j)-Y(i,j))*(X(q[r-1])-X(q[r])))r--;
q[++r]=i;
}
}
cout<<-SumX[n]*SumX[n]+m*f[n][m]<<endl;
return 0;
}
这题我犯了一个很大的错误
我不应该直接开始设状态，写方程的
先对方差进行分析，再写方程，会简洁不知道多少
这其实已经算是方差的性质了，要狠狠的记住啊，再写方程前，尽可能化简!