洛谷链接 分析 首先给出朴素的方程( s [ i ] = ∑ j = 1 i x [ j ] s[i]=\sum_{j=1}^{i}x[j] s[i]=∑j=1i​x[j]) d p [ i ] = m i n { d p [ j ] + a ( s [ i ] − s [ j ] ) 2 + b ( s [ i ] − s [ j ] ) + c } dp[i]=min\{dp[j]+

点击这里查看原题 DP方程： f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c) 如果j>k且j比k更优，则 f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i] /*User:SmallLanguage:C++P