首页 > 代码库 > bjoj1911 [Apio2010] 序列分割
bjoj1911 [Apio2010] 序列分割
1911: [Apio2010]特别行动队
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 4486 Solved: 2140
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
-1 10 -20
2 2 3 4
Sample Output
9
HINT
Source
转化条件,挖掘深入信息,答案其实就是等于k+1段两两相乘(乘法原理YY),与切的顺序无关,ans=ΣCj * (Ci-Cj);; (ans=∑ans=∑第 i 段×前 i-1 段的和);所以根据k的阶段来动态规划,令f[i][j]表示将前 j 个数分成 i 段的最大得分,那么就有f[i][j]=max{f[i?1][k]+C[k]×(C[j]?C[k])};然后使用滚动数组,斜率优化:注意C[i]有可能为0,(式子中有0),所以不用getx,用cale()函数相乘;
1 #include<algorithm> 2 #include<iostream> 3 #include<iomanip> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cstdio> 7 #include<vector> 8 #include<cmath> 9 #include<queue> 10 #include<stack> 11 #include<map> 12 #include<set> 13 #define ll long long 14 #define rep(i,a,b) for(register int i=a;i<=b;++i) 15 #define re register 16 using namespace std; 17 const int N=100010; 18 ll dp[2][N],C[N]; 19 int n,q[N]; 20 inline ll gi( ) 21 { 22 ll ret=0;char ch=getchar(); 23 while(ch<‘0‘||ch>‘9‘) ch=getchar(); 24 while(ch>=‘0‘&&ch<=‘9‘) ret=ret*10+ch-‘0‘,ch=getchar(); 25 return ret; 26 } 27 ll getnum(int now,int i,int bj) { 28 return dp[!bj][i] + C[i]*(C[now]-C[i]); 29 } 30 bool cale(int l1,int l2,int l3,int bj) { 31 ll b1= dp[!bj][l1]-C[l1]*C[l1],b2=dp[!bj][l2] - C[l2]*C[l2] , b3=dp[!bj][l3] - C[l3]*C[l3];// bug 32 return (b3-b2)*(C[l1]-C[l2]) <= (b2-b1)*(C[l2]-C[l3]); 33 } 34 int main( ) 35 { 36 37 n=gi();int k=gi(); 38 rep(i,1,n) C[i]=gi(),C[i]+=C[i-1]; 39 re int bj=1,hd,tl; 40 for(re int u=1;u<=k;u++) { 41 bj=!bj; 42 hd=tl=0;q[0]=0; 43 for(re int i=1;i<=n;i++) { 44 while(hd+2<=tl&&cale(q[tl-2],q[tl-1],q[tl],bj)) q[tl-1]=q[tl--];// 45 while(hd<tl&&getnum(i,q[hd],bj)<=getnum(i,q[hd+1],bj)) hd++; 46 dp[bj][i]=getnum(i,q[hd],bj); 47 q[++tl]=i; 48 } 49 } 50 printf("%lld",dp[bj][n]); 51 return 0; 52 }
bjoj1911 [Apio2010] 序列分割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。