我的理解：
備注：(i)代表只含i未知數的式子
形如以下表達式的狀態轉移：
dp[i]=dp[j]+(j,i);
dp[i]=dp[k]+(k,i);
假設對於i狀態時，選擇j狀態比選擇k狀態更優.
那麼dp[j]+(j,i)
如果上式可以轉化成:dp[j]+(j)-(dp[k]+(k))/(j)-(k)<(i)
那麼就可以用斜率優化進行優化：
設g[j,k]<(i)代表在i狀態時，選擇j狀態比選擇k狀態更優。
對於g[i][j]
如果g[i][j]<(i),那麼i狀態比j狀態更優，則拋棄j狀態。
如果g[i][j]>=(i),那麼g[j][k]>=(i),那麼k狀態比j狀態要優，那麼拋棄j狀態。
即：
如果存在g[i][j]
#include
#include
#include
#include
using namespace std;
#define maxn 550000
struct list
{
int x;
int val;
} node[maxn],p;
int a[maxn];
int sum[maxn];
int dp[maxn];
int gety(int x,int y)
{
return dp[x]+sum[x]*sum[x]-dp[y]-sum[y]*sum[y];
}
int tan(int x,int y,int z)
{
int ay=gety(z,y);
int by=gety(y,x);
int ax=2*(sum[z]-sum[y]);
int bx=2*(sum[y]-sum[x]);
if(ay*bx<=by*ax)return 1;
return 0;
}
int pan(int a,int b,int c)
{
int ay=gety(b,a);
int ax=2*(sum[b]-sum[a]);
if(ay<=sum[c]*ax)return 1;
return 0;
}
int main()
{
int n,m,i;
while(~scanf(%d%d,&n,&m))
{
sum[0]=0;
for(i=1; i<=n; i++)
{
scanf(%d,&a[i]);
sum[i]=sum[i-1]+a[i];
}
int head,tail;
head=1;
tail=0;
p.x=0;
node[++tail]=p;
memset(dp,0,sizeof(dp));
for(i=1; i<=n; i++)
{
p.x=i;
while(tail>head&&pan(node[head].x,node[head+1].x,i))head++;
int x=node[head].x;
dp[i]=dp[x]+m+(sum[i]-sum[x])*(sum[i]-sum[x]);
while(tail>head&&tan(node[tail-1].x,node[tail].x,i))tail--;
node[++tail]=p;
}
cout<
