P3648 [APIO2014] 序列分割
第一次做斜率优化的题
题解看懂了，但没有完全看懂
等以后得回来看一次
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll n,k,vis[205][100007];
ll s[100007],f[100007],g[100007];
int dl[100007],hd,tl;
double pd(int x,int y)
{
ll x1=-s[x];
ll y1=g[x]-s[x]*s[x];
ll x2=-s[y];
ll y2=g[y]-s[y]*s[y];
if(x1==x2) return -1e10;
return (double)((double)(y2-y1)/(double) (x2-x1));
}
int main()
{
scanf("%lld%lld",&n,&k);
for1(i,1,n)
{
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
ll ji;
for1(t,1,k)
{
for1(i,1,n) g[i]=f[i];
hd=tl=0;
for1(i,1,n)
{
while(tl-hd>=2&&pd(dl[hd],dl[hd+1])<=s[i]) hd++;
f[i]=0;
if(hd<tl)
{
ji=dl[hd];
vis[t][i]=ji;
f[i]=g[ji]+s[ji]*(s[i]-s[ji]);
}
while(tl-hd>=2&&pd(dl[tl-1],dl[tl-2])>=pd(i, dl[tl-1])) tl--;
dl[tl++]=i;
}
}
printf("%lld\n",f[n]);
ll i=vis[k][n];
while(k)
{
printf("%lld ",i),
i=vis[--k][i];
}
return 0;
}