「SDOI2016」征途 TJ
题目大意：
有 \(n\) 个块，给出其块长，将其分为 \(m\) 组，使得 每组内长度之和 的方差最小。
输出 \(v \times m^2\)，其中 \(v\) 是方差。
思路：
方差是什么？我没学过。
首先给一下方差的定义，防止忘了的同学。
统计中的方差（样本方差）是每个样本值与全体样本值的平均数之差的平方值的平均数
说白了，记 \(x\) 为数列 \(a\) 的平均数，构造数列 \(b\) 使得 \(b_i=(a_i-x)^2\)，方差就是 \(b\) 数列中的平均数。
看到这种没见过的数论问题，我们首先考虑当个老老实实的 ctjer。
记 \(v\) 为方差，\(r_i\) 为第 \(i\) 组的长度，\(\overline r\) 为 \(r\) 数组的平均数。
则有：
\[\begin{aligned} v &= \frac{\sum_{i=1}^m (r_i-{\overline r})^2}{m} \\ &= \frac{\sum_{i=1}^m (r_i^2+ {\overline r}^2 - 2 \times r_i \times {\overline r})}{m}\\ &= \frac{m \times {\overline r}^2 + \sum_{i=1}^m r_i^2 - 2 \times {\overline r} \times \sum_{i=1}^m r_i}{m} \\ &= \frac{m \times (\frac{\sum_{i=1}^m r_i}{m})^2 + \sum_{i=1}^m r_i^2 - 2 \times (\frac{\sum_{i=1}^m r_i}{m}) \times \sum_{i=1}^m r_i}{m} \\ &= \frac{\frac{(\sum_{i=1}^m r_i)^2}{m} + \sum_{i=1}^m r_i^2 - 2 \times \frac{(\sum_{i=1}^m r_i)^2}{m}}{m} \\ &= \frac{\sum_{i=1}^m r_i^2}{m} - \frac{(\sum_{i=1}^m r_i)^2}{m} \end{aligned} \]（这柿子真不是人打的）
要求答案为：
\(v \times m^2 = m^2 \times (\frac{\sum_{i=1}^m r_i^2}{m} - \frac{(\sum_{i=1}^m r_i)^2}{m^2})=m \times \sum_{i=1}^m r_i^2 + (\sum_{i=1}^m r_i)^2\)
瞪眼法，可以发现后者就是我们所有块的总长度，则只需解决 \(\sum_{i=1}^mr_i^2\)，下文记为 \(now\)。
设 \(dp_{i,j}\) 表示考虑前 \(i\) 块，第 \(i\) 块是第 \(j\) 组最后一个时，\(now\) 的最小值。
暴力转移：\(dp_{i,j}=\min_{k=0}^{i-1}(dp_{k,j-1}+(sum_k-sum_i)^2)\)，其中 \(sum_i\) 为块长的前缀和。
这个复杂度是 \(n^2\) 的，只能有 \(70pts\)，可以滚动数组 0/1 滚一下，得到 \(90pts\)，当然，还可以用类似于 01 背包的方法，倒序循环 \(k\)，直接压到一维，不过仍然是 \(90pts\)。
这里给出后两种代码：
//滚动数组
read(n,m);
for(int i=1;i<=n;++i) read(sum[i]),sum[i]+=sum[i-1];
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int j=1;j<=m;++j){
for(int i=1;i<=n;++i){
for(int k=0;k<i;++k){
dp[j&1][i]=min(dp[j&1][i],dp[(j&1)^1][k]+(sum[k]-sum[i])*(sum[k]-sum[i]));
}
}
}
ans=m*dp[m&1][n]-sum[n]*sum[n];
write(ans);
//直接压成一维
read(n,m);
for(int i=1;i<=n;++i) read(sum[i]),sum[i]+=sum[i-1];
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int j=1;j<=m;++j){
for(int i=n;i>=1;--i){
for(int k=0;k<i;++k){
dp[i]=min(dp[i],dp[k]+(sum[k]-sum[i])*(sum[k]-sum[i]));
}
// for(int k=0;k<i;++k){
// dp[j&1][i]=min(dp[j&1][i],dp[(j&1)^1][k]+(sum[k]-sum[i])*(sum[k]-sum[i]));
// }
}
}
write(m*dp[n]-sum[n]*sum[n]);
优化：
我们发现这个暴力已经压榨到极限了，\(90pts\) 是最高了。
考试的时候当然可以大胆走人，不过平时还是要正解 A 掉。
我们去掉最值符号，对方程变式：
\[\begin{aligned} dp_{k,j-1} &= dp_{i,j}-(sum_k-sum_i)^2 \\ &= dp_{i,j}-sum_k^2-sum_i^2+2 \times sum_k \times sum_i \\ \end{aligned} \]此时发现方程左右都包含 \(k\)，但右侧有俩，我们移一个 \(sum_k^2\)。
\[dp_{k,j-1} + sum_k^2 = 2 \times sum_i \times sum_k + dp_{i,j}-sum_i^2 \]现在使用瞪眼法，不难发现，\(2 \times sum_i\) 是斜率，\(dp_{i,j}-sum_i^2\) 是截距。
由于 \(sum_k\) 单调递增，所以 \(sum_k^2\) 也是单调递增的，因此求得截距最小时 \(dp_{k,j-1}\) 也取得最小值，用单调队列维护一个对应的下凸壳，套任务安排2的模板即可。
要是您实在懒得，我就这么写上来吧：
- 原本是：\(dp_{k1,j-1}+sum_{k1}^2+sum_i^2-2\times sum_{k1} \times sum_i < dp_{k2,j-1} + sum_{k2}^2 + sum_i^2 - 2 \times sum_{k2}\times sum_i\)
- 变式得到：\((dp_{k1,j-1}+sum_{k1}^2)-(dp_{k2,j-1}+sum_{k2}^2) < 2 \times sum_i \times (sum_{k1}-sum_{k2})\)
这个就可以拿去队尾踢人了，队首同理。
最后答案就是 \(m \times dp_{n,m} +now\)。
细节：
- 要开 long long。
- 不要压成一维，转移和决策范围的方向是反着的，只能两个数组之间滚动。
dp[0][0]=dp[1][0]=0，lws踩过此坑。- 单调队列最初插入个 0
，相信大家都踩过，在不同的题。 - 建议把一些长得不能说是很像，只能说是除了参数一模一样的部分封装一下，丢进函数看起来就没那么伤眼睛。
lyh：你是懂封装的。
Code：
（可以拿走，我是指缺省源）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<initializer_list>
using ll=long long;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define flush() fwrite(obuf,p3-obuf,1,stdout)
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(flush(),p3=obuf,*p3++=x)
#define out_end (flush(),0)
template<typename T> inline void read(T&);
template<typename T> inline void write(T);
inline void read(char*);
inline void write(char);
inline void write(const char*);
template<typename... Args> inline void read(Args&...);
template<typename... Args> inline void write(Args...);
template<typename Type> const Type& max(const Type& x,const Type& y){return x<y?y:x;}
template<typename Type> const Type& min(const Type& x,const Type& y){return x<y?x:y;}
const int N=3005;
int n,m,sum[N],que[N],head,tail;
ll dp[2][N];
inline ll calc(int i,int k){return dp[(i&1)^1][k]+sum[k]*sum[k];}
inline int get(int k){return sum[k]<<1;}
signed main(){
read(n,m);
for(int i=1;i<=n;++i) read(sum[i]),sum[i]+=sum[i-1];
memset(dp,0x3f,sizeof dp);
dp[0][0]=dp[1][0]=0;
for(int j=1;j<=m;++j){
que[head=tail=1]=0;
for(int i=1;i<=n;++i){
while(head<tail&&(calc(j,que[head+1])-calc(j,que[head]))<=sum[i]*(get(que[head+1])-get(que[head]))) ++head;
dp[j&1][i]=calc(j,que[head])-get(que[head])*sum[i]+sum[i]*sum[i];
while(head<tail&&(calc(j,que[tail])-calc(j,que[tail-1]))*(get(i)-get(que[tail]))>=(calc(j,i)-calc(j,que[tail]))*(get(que[tail])-get(que[tail-1]))) --tail;
que[++tail]=i;
}
}
write(m*dp[m&1][n]-sum[n]*sum[n]);
return out_end;
}
template<typename T> inline void read(T& x){
x=0;bool flag=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)-(ch&15);
else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
template<typename T> inline void write(T x){
static char sta[40];
int top=0;
if(x<0){
putchar('-');
do sta[top++]=((-x)%10)^48,x/=10;
while(x);
}
else{
do sta[top++]=(x%10)^48,x/=10;
while(x);
}
while(top) putchar(sta[--top]);
}
inline void read(char* str){while((*str=getchar())==' '||*str=='\n');while((*++str=getchar())!=' '&&*str!='\n');*str=0;}
inline void write(char x){putchar(x);}
inline void write(const char* str){while(*str!='\0') putchar(*str++);}
template<typename... Args> inline void read(Args& ...args){(void)std::initializer_list<int>{(read(args),0)...};}
template<typename... Args> inline void write(Args ...args){(void)std::initializer_list<int>{(write(args),0)...};}