題解：
不考慮那麼大的數據范圍，首先我們可以想出它的dp解法，dp[ｉ][ｋ]表示前ｉ個數字分成ｋ段的最大分值，那麼轉移方程則為：
dp[ｉ][ｋ]=max(dp[ｊ][ｋ-1]+sum[ｊ]*(sum[ｉ]-sum[ｊ]));
然而這樣做的話很明顯是k×n^2的算法，對於100000的數據來說即使ｋ只有200也是會超時的，因此我們要想辦法降低一維復雜度使得算法變為ｎ×ｋ的復雜度，而降低動態規劃復雜度一般都是通過降低狀態轉移的那一維即枚舉ｊ的復雜度，這就用到了斜率優化。
根據斜率優化一貫的做法，假如存在兩個決策點k1,k2且k1 < k2，設在更新i點的dp值dp[i][t+1]時k2優於k1，則存在：
dp[k1][t]+sum[k1]?(sum[i]?sum[k1])
將這個不等式變化之後得到：
(dp[k1][t]-sum[k1]^2)-(dp[k2][t]-sum[k2]^2)
_________________________________________
記slope[ k1，k2 ] =左邊的式子，那麼我們發現有兩個性質：
１．當 slope[ k1,k2 ] < sum[i]時對於ｉ點來說k2決策優於k1且永遠優於k1，因為序列中的每一個數都是非負數，對於任意ｘ> i來說 sum[x]>=sum[i] 當 slope[ k1,k2 ] < sum[i] 時一定有 slope[ k1,k2 ] < sum[ｘ] 因此每一個決策都具有單調性，即當 slope[ k1,k2 ] < sum[i] ，那麼對於ｉ以後的點k1永遠沒用。
２．若存在k1，k2，k3且k1 < k2 < k3，當slope[ k1,k2 ] >slope[ k2,k3 ]時，k2這個決策點永遠不會用到，為什麼呢？因為，假如在更新某一個點ｉ時如果k2比k1優，那麼slope[ k1,k2 ] < sum[i] 但同時因為 slope[ k1,k2 ] >slope[ k2,k3 ] 那麼 slope[ k2,k3 ] < sum[i] 即k3比k2優，所以k2沒用，假如k2沒有k1優，那麼k2直接就沒用了，因此不管怎樣k2都是沒用的。
擁有這兩個性質之後，我們需要維護一個隊列每次都只存有用的決策點來減少決策那一維的時間復雜度。根據２號性質，我們發現維護的隊列q必須符合這樣一個性質，即 slope[ q1,q2 ] < slope[ q2,q3 ] < slope[ q3,q4 ] <…………，否則隊列就出現了永遠無用的決策點。
如何構造這個隊列呢？
附代碼：
#include
#include
#include
#define maxn (100005)
using namespace std;
int n,m,k,q[maxn];
long long sum[maxn],dp[maxn][2],y[maxn][2];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
}
for (int i=1;i<=n;i++)
y[i][0]=0-sum[i]*sum[i];//dp[i][0]=0
for (int i=1;i<=k;i++)
{
int now=i%2;
int pre=(i+1)%2;
int h=1,t=1;
q[h]=1;
for (int j=1;j<=n;j++)
{
while(h=(y[q[h]][pre]-y[q[h+1]][pre])) h++;
dp[j][now]=dp[q[h]][pre]+sum[q[h]]*(sum[j]-sum[q[h]]);
y[j][now]=dp[j][now]-sum[j]*sum[j];
while(h=(y[q[t]][pre]-y[j][pre])*(sum[q[t]]-sum[q[t-1]]))t--;
t++;q[t]=j;
}
}
printf("%lld\n",dp[n][k%2]);
}
bzoj上管理員太懶不用記錄路徑，uoj上代碼：
#include
#include
#include
#define maxn (100005)
using namespace std;
int n,m,k,q[maxn],pr[maxn][202];
long long sum[maxn],dp[maxn][2],y[maxn][2];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
}
for (int i=1;i<=n;i++)
y[i][0]=0-sum[i]*sum[i];//dp[i][0]=0
for (int i=1;i<=k;i++)
{
int now=i%2;
int pre=(i+1)%2;
int h=1,t=1;
q[h]=0;
for (int j=1;j<=n;j++)
{
while(h=(y[q[h]][pre]-y[q[h+1]][pre])) h++;
pr[j][i]=q[h];
dp[j][now]=dp[q[h]][pre]+sum[q[h]]*(sum[j]-sum[q[h]]);
y[j][now]=dp[j][now]-sum[j]*sum[j];
while(h=(y[q[t]][pre]-y[j][pre])*(sum[q[t]]-sum[q[t-1]]))t--;
t++;q[t]=j;
}
}
cout<
