题目大意
题目分析
这难度还省选？套个cdq分治如何？
后面一段是定值，故只需要使$\sum_{i=1}^mx_i^2$最小即可。
设$f[i,j]$为前$i$天走了$j$段路的$\sum_{i=1}^mx_i^2$的最小值。
其中$sum[]$表示前缀和。
展开后就是一个裸的斜率优化了。
以$f[i-1,k]+s[k]^2$为纵坐标$y$，以$s[k]$为横坐标$x$，以$2s[j]$为斜率$k$，维护下凸包即可。
另，此题为资源分配类动态规划，因此还可以使用四边形不等式来优化状态转移。在实际测试中四边形不等式跑得快一些。
另，这道题在我们oj数据好像有点问题，要出玄学错误，建议新建$a[]$数组保存读入值。
代码
我的斜率优化1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=3005;
int n,m;
LL sum[maxn],a[maxn],f[maxn][maxn],Q[maxn];
double Slope(int i,int j,int con) {
return (double)(f[con][i]+sum[i]*sum[i]-f[con][j]-sum[j]*sum[j])/(sum[i]-sum[j]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1; i<=m; i++) {
int Left=1,Right=1;
Q[Left]=0;
for(int j=1; j<=n; j++) {
while(Left<Right&&Slope(Q[Left],Q[Left+1],i-1)<=2*sum[j])Left++;
int k=Q[Left];
f[i][j]=f[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]);
while(Left<Right&&Slope(Q[Right-1],Q[Right],i-1)>=Slope(Q[Right],j,i-1))Right--;
Q[++Right]=j;
}
}
printf("%lld\n",f[m][n]*m-sum[n]*sum[n]);
return 0;
}
KEKE_046的四边形不等式1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
const int maxn=3005;
int N,M;
int S[maxn];
int F[maxn][maxn];
int K[maxn][maxn];
int sqr(int x){return x*x;}
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++){
int x=0;scanf("%d",&x);
S[i]=S[i-1]+x;
}
memset(F,0x3f,sizeof F);
F[0][0]=0;
for(int i=1;i<=M;i++){
K[i][N+1]=N-1;
for(int j=N;j>=i;j--){
for(int k=K[i-1][j];k<=K[i][j+1];k++){
int t=F[i-1][k]+sqr(S[j]-S[k]);
if(t<F[i][j]){F[i][j]=t;K[i][j]=k;}
}
}
}
cout<<F[M][N]*M-S[N]*S[N];
return 0;
}
