題目連接: http://new.tyvj.cn/Problem_Show.aspx?id=1215
思路:
方程再簡單不過了:
dp[i]表示以第i個人為某一組最后一個人的總戰斗值
dp[i]=max(dp[j]+F(sum[i]-sum[j]))
其中F(x)=A*x*x+B*x+C ? ? ? sum[i]表示戰斗值的前綴和
顯然n^2的方程,只能得到20分
?
單調性顯然,那么就開始我們的斜率優化
設j<k且滿足k比j更優
dp[j]+A*(sum[i]-sum[j])^2+B*(sum[i]-sum[j])+C<=dp[k]+A*(sum[i]-sum[k])^2+B*(sum[i]-sum[k])+C
化簡,分離變量,將含j,k的結構放到方程一邊,含i的結構放在方程另一邊:
2*A*sum[i]*(sum[k]-sum[j])<=dp[k]-dp[j]+B*(sum[j]-sum[k])+A*(sum[k]^2-sum[j]^2)
設:
p[i]=2*A*sum[i]
G(k,j)=dp[k]-dp[j]+B*(sum[j]-sum[k])+A*(sum[k]^2-sum[j]^2)
S(k,j)=sum[k]-sum[j]
W(k,j)=G(k,j)/S(k,j)
所以只要維護 ? : ? W(k,j)>=p[i] ? 就可以了~
(PS:如果沒有看懂斜率優化,請轉步: http://www.cnblogs.com/proverbs/archive/2012/10/06/2713109.html )
?
?

1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 6 #define N 1001000 7 8 using namespace std; 9 10 __int64 A,B,C,a[N],sum[N],dp[N],p[N]; 11 int n,q[N]; 12 13 void read() 14 { 15 scanf( " %d " ,& n); 16 scanf( " %I64d%I64d%I64d " ,&A,&B,& C); 17 for ( int i= 1 ;i<=n;i++ ) 18 { 19 scanf( " %I64d " ,& a[i]); 20 sum[i]=sum[i- 1 ]+ a[i]; 21 p[i]= 2 *A* sum[i]; 22 } 23 } 24 25 inline __int64 G( int y, int x) 26 { 27 return dp[y]-dp[x]+B*(sum[x]-sum[y])+A*(sum[y]*sum[y]-sum[x]* sum[x]); 28 } 29 30 inline __int64 S( int y, int x) 31 { 32 return sum[y]- sum[x]; 33 } 34 35 inline __int64 F( int x) 36 { 37 return A*x*x+B*x+ C; 38 } 39 40 void go() 41 { 42 dp[ 0 ]= 0 ; 43 int h= 1 ,t= 1 ; 44 q[t++]= 0 ; 45 for ( int i= 1 ,x,y,z;i<=n;i++ ) 46 { 47 while (h<t- 1 &&G(q[h+ 1 ],q[h])>=p[i]*S(q[h+ 1 ],q[h])) h++ ; 48 49 dp[i]=dp[q[h]]+F(sum[i]- sum[q[h]]); 50 51 q[t++]= i; 52 53 for ( int j=t- 2 ;j- 1 >=h;j-- ) 54 { 55 x=q[j- 1 ]; y=q[j]; z=q[j+ 1 ]; 56 if (G(z,y)*S(y,x)>=G(y,x)*S(z,y)) q[j]=q[-- t]; 57 else break ; 58 } 59 } 60 printf( " %I64d\n " ,dp[n]); 61 } 62 63 int main() 64 { 65 read(); 66 go(); 67 return 0 ; 68 }
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
