Description

　　小H最近迷上了一個分割序列的游戲。在這個游戲里，小H需要將一個長度為N的非負(fù)整數(shù)序列分割成k+l個非空的子序列。為了得到k+l個子序列， 小H將重復(fù)進行七次以下的步驟：
　　1．小H首先選擇一個長度超過1的序列（一開始小H只有一個長度為n的
序列一一也就是一開始得到的整個序列）；
　　2．選擇一個位置，并通過這個位置將這個序列分割成連續(xù)的兩個非空的新
序列。
　　每次進行上述步驟之后，小H將會得到一定的分?jǐn)?shù)。這個分?jǐn)?shù)為兩個新序
列中元素和的乘積。小H希望選擇一種最佳的分割方案，使得k輪（次）之后，
小H的總得分最大。

Input

　　輸入文件的第一行包含兩個整數(shù)n和尼(k+1≤n)。
　　第二行包含n個非負(fù)整數(shù)a1，n2…．，an(0≤ai≤10^4)，表示一開始小H得
到的序列。

Output

　　一行包含一個整數(shù)，為小H可以得到的最大得分。

Sample Input

7 3
4 1 3 4 0 2 3

Sample Output

108

HINT

【樣例說明】

在樣例中，小H可以通過如下3輪操作得到108分：

　　1．-開始小H有一個序列(4，1，3，4，0，2，3)。小H選擇在第1個數(shù)之后的位置，將序列分成兩部分，并得到4×(1+3+4+0+2+3)=52分。
　　2．這一輪開始時小H有兩個序列：(4)，(1，3，4，0，2，3)。小H選擇在第3個數(shù)字之后的位置將第二個序列分成兩部分，并得到(1+3)×(4+0+2+ 3)=36分。
　　3．這一輪開始時小H有三個序列：(4)，(1，3)，(4，0，2，3)。小H選擇在第5個數(shù)字之后的位置將第三個序列分成兩部分，并得到(4+0)×(2+3)=20分。
　　經(jīng)過上述三輪操作，小H將會得到四個子序列：(4)，(1，3)，(4，0)，(2，3)并總共得到52+36+20=108分。

【數(shù)據(jù)規(guī)模與評分】 ：數(shù)據(jù)滿足2≤n≤100000,1≤k≤min(n -1，200)。

?

　　這題記前綴和為s，當(dāng)前狀態(tài)f[i]，則狀態(tài)轉(zhuǎn)移方程是f[i]=max(f[j]+s[j]*(s[i]-s[j]))，如果推到這一步，這道題就差不多解決了。

　　使用斜率優(yōu)化的技巧然后加上滾動數(shù)組，就可以很懸地AC了（斜率優(yōu)化的DP是半正解）~~~

　　1A的哦~，長長的26行好蛋疼啊~

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int maxn=100010; 6 long long dp[maxn][2]; 7 long long s[maxn]; 8 int q[maxn],front,back; 9 int main(){ 10 int n,K; 11 scanf("%d%d",&n,&K);K++; 12 for(int i=1;i<=n;i++){ 13 scanf("%lld",&s[i]); 14 s[i]+=s[i-1]; 15 } 16 int now,pre; 17 for(int k=2;k<=K;k++){ 18 now=(k+1)%2; 19 pre=k%2; 20 front=back=1; 21 q[back++]=0; 22 for(int i=1;i<=n;i++){ 23 while(front<back-1&&dp[q[front+1]][pre]-dp[q[front]][pre]+(s[q[front+1]]-s[q[front]])*s[i]-s[q[front+1]]*s[q[front+1]]+s[q[front]]*s[q[front]]>=0) 24 front++; 25 dp[i][now]=dp[q[front]][pre]+s[q[front]]*(s[i]-s[q[front]]); 26 while(front<back-1&&(dp[i][pre]-dp[q[back-1]][pre]-s[i]*s[i]+s[q[back-1]]*s[q[back-1]])*(s[q[back-2]]-s[q[back-1]])<=(dp[q[back-1]][pre]-dp[q[back-2]][pre]-s[q[back-1]]*s[q[back-1]]+s[q[back-2]]*s[q[back-2]])*(s[q[back-1]]-s[i])) 27 back--; 28 q[back++]=i; 29 } 30 } 31 printf("%lld\n",dp[n][now]); 32 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TenderRun/p/5284349.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的动态规划(斜率优化)：BZOJ 3675 [Apio2014]序列分割的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。