斜率优化。假如我讲不清楚就去%吧

我一开始想了个O(kn^3)的

就是枚举k和n，然后枚举前面的点，然后枚举前面的点到当前点在哪断最优。

而O(kn^2)咋搞呢

我通过画图发现（其实是某人告诉了我分配律的问题）

样例最后断出来是这样的

(4)，(1，3)，(4，0)，(2，3)

然后答案其实就是每一个数和其他不同组的数乘一次

DP方程就得出是这样的：f[i][now]=f[j][now^1]+s[j]*(s[i]-s[j]);

其中now是滚动数组滚动枚举k的t

然后斜率优化。

但是有一个狗比问题，就是s[j1]==s[j2]，这时除数为0要特判

星感大神说他调样例的时候发现的。

然而我的就玄学过了样例。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;LL a[110000],s[110000],f[110000][2];int now;double Y(int j){ return double(f[j][now^1]-s[j]*s[j]);}double X(int j){ return double(s[j]);}double slope(int j1,int j2){ return (Y(j1)-Y(j2))/(X(j2)-X(j1));}int head,tail,list[110000];int main(){ int n,m; scanf("%d%d",&n,&m); s[0]=0; for(int i=1;i<=n;i++) scanf("%lld",&a[i]), s[i]=s[i-1]+a[i]; memset(f,0,sizeof(f));now=0; for(int t=1;t<=m;t++)//第t次 cut { now^=1; head=1,tail=1;list[head]=t; for(int i=t+1;i<=n;i++) { while(head!=tail&&(slope(list[head],list[head+1])
           
            slope(list[tail],i)))tail--; list[++tail]=i; } } printf("%lld\n",f[n][now]); return 0;}