@[reclusive](/user/654281) 大概是 求出来的直线的截距中，$f$ 的系数为负数。
by zzxLLL @ 2023-08-18 09:08:06
@[reclusive](/user/654281)
by 李湛然 @ 2023-08-25 15:36:50
改成+1e18
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
typedef long long ll;
int n,k;
ll f[N],s[N],g[N];
inline ll X(int u){
return s[u];
}
inline ll Y(int u){
return g[u]-s[u]*s[u];
}
inline double slope(int u,int v){
if(s[u]==s[v])return (long long)1000000000000000000;
return 1.0*((1.0*(Y(u)-Y(v)))/(1.0*(X(u)-X(v))));
}
int q[N],lst[N][201],a[N],cnt;
int main(){
register int i;
cin>>n>>k;
for(i=1;i<=n;++i)scanf("%lld",&s[i]),s[i]+=s[i-1];
for(int tim=1;tim<=k;++tim){
int h=1,t=1;
memset(q,0,sizeof(q));
for(i=1;i<=n;++i){
while(h<t && slope(q[h],q[h+1])>=-s[i])
{
h++;
}
f[i]=g[q[h]]+s[q[h]]*(s[i]-s[q[h]]);
lst[i][tim]=q[h];
while(h<t&&slope(q[t-1],q[t])<=slope(q[t],i))t--;
q[++t]=i;
}
for(i=1;i<=n;++i)g[i]=f[i];
}
cout<<f[n]<<endl;
int p=n;
while(p){
a[++cnt]=p;
p=lst[p][k];
k--;
}
for(i=cnt;i>=2;i--)printf("%d ",a[i]);
return 0;
}
```
by 李湛然 @ 2023-08-25 15:42:17
@[reclusive](/user/654281) @[李湛然](/user/195705) 上凸包这两种写法都能AC，但是严格来说下面的是对的吧
```cpp
if(X(i)==X(j)) return INF;
```
```cpp
if(X(i)==X(j)) return (Y(i)<=Y(j)?INF:-INF);
```
\
我把<=写成<
都WA了
by TigerNick @ 2024-01-31 20:43:42