include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[10000],s[6100],q[10000];
int slope(int j,int k)
{
int x=(dp[j]-dp[k]+s[j]s[j]-s[k]s[k])/(s[j]+s[k]);
return x;
}//求斜率
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
}
int L=1,R=1;
dp[0]=0;
for(int i=1;i<=n;i++)
{
while(L<R && slope(q[L],q[L+1])<=s[i])L++;
dp[i]=dp[q[L]]+(s[i]-s[q[L]])(s[i]-s[q[L]])+m;
while(L<R && slope(q[R-1],q[R])>slope(q[R],i))R--;
q[++R]=i;
}
cout<<dp[n]<<endl;
}
return 0;
}
/斜率优化:
1.将转移方程抽象成一个不等式关系,
如本题中由于要求出最小价值,易知转移方程为:dp[i]=min(dp[j-1]+(s[i]-s[j])^2+m) (1<=j<=i)
设此时有两个点,j和k
则如果有dp[j]+(s[i]-s[j])2+m<dp[k]+(s[i]-s[k])2+m
即可知道j优于k
将上不等式展开可得:
dp[j]+s[i]2+s[j]2-2s[i]s[j]<dp[k]+s[i]2+s[k]2-2s[i]s[k];
移项:dp[j]-dp[k]+s[j]2-s[k]2<2s[i]s[j]-2s[i]s[k]
整理:(dp[j]-dp[k]+s[j]2-s[k]2)/(s[j]-s[k])<2s[i];
因为s[i]可看作常数,而左边可抽象成(y1-y2)/(x1-x2)
即斜率,那么只要满足k与j之间斜率满足此不等式,则就有j优于k
若不等号方向改变,则为k优于j
那么求斜率的函数则为
int slope(int j,int k)
{
int x=(dp[j]-dp[k]+s[j]s[j]-s[k]s[k])/(s[j]+s[k]);
return x;
}
2.求得斜率后,便有三种情况(j,k,i)
一,三个点的两条连线斜率均小于2s[i],则分别比较两个斜率,斜率更大的右端点为最优点
二,三个点的两条连线斜率均大于2s[i],则分别比较两个斜率,斜率更大的左端点为最优点
三,三个点的两条连线斜率一大一小,则可以判断的是中间一个点一定不是最优点,可排除
3.排除完后,可发现这些点是成单调递增趋势的,将这些点放入队列中
依次查找符合要求的点
本题中最优点应为满足斜率<2s[i]且位于最右边的点
*/