rt.

最开始我做的时候，想到有些状态是得不到的，所以将 dp 数组初始全赋为 $-\infty$，但是寄了；然后把初始化语句删掉之后就能过，为什么？

直观上理解，一些状态是得不到的，也就无法转移出去，不应该赋为负无穷吗？

WA code：

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e5+5,M=2e2+5;
int f[N][M],pre[N][M],s[N],a[N],n,k;
int x(int i) {
    return s[i];
}
int y(int i,int j) {
    return s[i]*s[i]-f[i][j-1];
}
ld slope(int i,int j,int k) {
	if(s[i]==s[j])
		return -INFLL;
    return 1.0*(y(j,k)-y(i,k))/(x(j)-x(i));
}
int q[N],head,tail;
void print(int i,int j) {
	if(j!=1)
		print(pre[i][j],j-1);
	printf("%lld ",pre[i][j]);
}
signed main() {
    scanf("%lld%lld",&n,&k);
    rep(i,1,n)
        scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    cl(f,0xaf); f[0][0]=0; //这里
    rep(j,1,k) {
        q[head=tail=1]=0;
        rep(i,1,n) {
            while(head<tail&&slope(q[head],q[head+1],j)<=s[i])
                ++head;
            int k=q[head];
            f[i][j]=f[k][j-1]+s[k]*(s[i]-s[k]);
			pre[i][j]=k;
            while(head<tail&&slope(q[tail-1],q[tail],j)>=slope(q[tail],i,j))
                --tail;
            q[++tail]=i;
        }
    }
    printf("%lld\n",f[n][k]);
	print(n,k);
    return 0;
}

AC code:

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e5+5,M=2e2+5;
int f[N][M],pre[N][M],s[N],a[N],n,k;
int x(int i) {
    return s[i];
}
int y(int i,int j) {
    return s[i]*s[i]-f[i][j-1];
}
ld slope(int i,int j,int k) {
	if(s[i]==s[j])
		return -INFLL;
    return 1.0*(y(j,k)-y(i,k))/(x(j)-x(i));
}
int q[N],head,tail;
void print(int i,int j) {
	if(j!=1)
		print(pre[i][j],j-1);
	printf("%lld ",pre[i][j]);
}
signed main() {
    scanf("%lld%lld",&n,&k);
    rep(i,1,n)
        scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    rep(j,1,k) {
        q[head=tail=1]=0;
        rep(i,1,n) {
            while(head<tail&&slope(q[head],q[head+1],j)<=s[i])
                ++head;
            int k=q[head];
            f[i][j]=f[k][j-1]+s[k]*(s[i]-s[k]);
			pre[i][j]=k;
            while(head<tail&&slope(q[tail-1],q[tail],j)>=slope(q[tail],i,j))
                --tail;
            q[++tail]=i;
        }
    }
    printf("%lld\n",f[n][k]);
	print(n,k);
    return 0;
}