您为什么要强调您是妹子呢0.0
by 靛涟 @ 2019-04-16 23:33:26
这个高亮好像不是cpp
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,maxk=210;
long long f[maxn],g[maxn],s[maxn];
int n,K1;
int pre[maxn][maxk],q[maxn];
double X(int i){
return s[i];
}
double Y(int i){
return g[i]-s[i]*s[i];
}
double K(int i,int j){
double mo=X(j)-X(i);
return !mo ? -1e18 : (Y(i)-Y(j))/mo;
}
int main(){
cin>>n>>K1;
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(int k=1;k<=K1;k++){
int head=1,tail=1;q[1]=0;
for(int i=1;i<=n;i++){
while(head<tail && K(q[head],q[head+1])<=s[i]) head++;
int j=q[head];
f[i]=g[j]+(s[i]-s[j])*s[j];
pre[i][k]=j;
while(head<tail && K(q[tail],q[tail-1])>=K(i,q[tail])) tail--;
q[++tail]=i;
}
memcpy(g,f,sizeof(g));
}
printf("%lld\n",f[n]);
for(int i=K1,u=n;i>=1;i--){
u=pre[u][i];
printf("%d ",u);
}
return 0;
}
```
by Smile_Cindy @ 2019-04-17 08:49:51
@[人殇物已非](/space/show?uid=64611)
斜率优化dp是吧？方程发一下
by Smile_Cindy @ 2019-04-17 08:50:17
@[Alpha](/space/show?uid=87058)
$-s[i]*s[j]+f[i]=g[j]-s[j]*s[j];$
$-s[i]=k$
$s[j]=x$
$f[i]=b$
$g[j]-s[j]*s[j]=y$
by 人殇物已非 @ 2019-04-17 08:57:09
@[Alpha](/space/show?uid=87058)
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,maxk=210;
long long f[maxn],g[maxn],s[maxn];
int n,K1;
int pre[maxn][maxk],q[maxn];
double X(int i){
return 1.0*s[i];
}
double Y(int i){
return 1.0*(g[i]-s[i]*s[i]);
}
double K(int i,int j){
return X(i)==X(j) ? -1e18 : (Y(i)-Y(j))/(X(i)-X(j));
}
int main(){
cin>>n>>K1;
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(int k=1;k<=K1;k++){
int head=1,tail=1;q[1]=0;
for(int i=1;i<=n;i++){
while(head<tail && K(q[head],q[head+1])>=-1.0*s[i]) head++;
int j=q[head];
f[i]=g[j]+(s[i]-s[j])*s[j];
pre[i][k]=j;
while(head<tail && K(q[tail],q[tail-1])<=K(i,q[tail])) tail--;
q[++tail]=i;
}
memcpy(g,f,sizeof(g));
}
printf("%lld\n",f[n]);
for(int i=K1,u=n;i>=1;i--){
u=pre[u][i];
printf("%d ",u);
}
return 0;
}
```
这是一开始的代码，是上凸壳，也是88pts，上面贴的那个是把斜率为负强行拉正然后维护下凸壳。
by 人殇物已非 @ 2019-04-17 09:00:16
新改的一些代码在提交记录里，到最后我感觉都和题解一模一样了。。。救救孩子。
by 人殇物已非 @ 2019-04-18 10:01:32
之前有同问题，开long double解决了
by mohei0 @ 2019-05-29 13:53:48
@[人殇物已非](/space/show?uid=64611)
by mohei0 @ 2019-05-29 13:54:19
@[墨黑0](/space/show?uid=34323) 蟹蟹，确实是被卡了精度，已经AC啦~
by 人殇物已非 @ 2019-05-31 17:40:56
@[人殇物已非](/space/show?uid=64611) 您好，请问您为什么要强调自己是妹子呢？
by chdy @ 2019-06-02 09:22:10