?
?
Max Sum of Max-K-sub-sequence
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5084????Accepted Submission(s): 1842
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.
?
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).
?
?
?
?
?
?
?
題目大意:T 組數據,求 n 個數 連續子串的最大和是多少,子串要求長度不超過 k,以及這是個環形,如果多解,滿足起點be最小,其次終點en最小
解題思路:枚舉每個起點be,終點en一定是在 be<=en<=be+k-1 這個范圍內,所以求這個范圍內的連續最長和即可,可以用 sum[en] -sum[be-1] ,其中sum[x]表示前x個數的和,所以即選出?be<=en<=be+k-1這個范圍內最大sum[i],用線段樹過了,但是rmq算法超時,郁悶!
線段樹算法,AC
?
#include <iostream> #include <cmath> #include <cstdio> using namespace std; const int maxn=200010; int d[maxn],sum[maxn],n,k,mx,mn; struct node{ int l,r,minc,maxc; }a[4*maxn]; void input(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&d[i]); d[i+n]=d[i]; } sum[0]=0; for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+d[i]; } void build(int l,int r,int k){ a[k].l=l; a[k].r=r; if(l<r){ int mid=(l+r)/2; build(l,mid,2*k); build(mid+1,r,2*k+1); a[k].maxc=max(a[2*k].maxc,a[2*k+1].maxc); a[k].minc=min(a[2*k].minc,a[2*k+1].minc); }else{ a[k].maxc=sum[l]; a[k].minc=sum[l]; } } void query(int l,int r,int k){ if(l<=a[k].l && a[k].r<=r){ //cout<<a[k].maxc<<" "<<a[k].minc<<endl; mx=max(mx,a[k].maxc); mn=min(mn,a[k].minc); }else{ int mid=(a[k].l+a[k].r)/2; if(r<=mid) query(l,r,2*k); else if(l>=mid+1) query(l,r,2*k+1); else{ query(l,mid,2*k); query(mid+1,r,2*k+1); } } } void computing(){ build(0,2*n,1); int ans=-(1<<30),be=1,en=1; for(int i=1;i<=n;i++){ mx=-(1<<30); query(i,i+k-1,1); if(mx-sum[i-1]>ans){ ans=mx-sum[i-1]; be=i; } } for(int i=be;i<=be+k-1;i++){ if(sum[i]-sum[be-1]==ans){ en=i; break; } } printf("%d %d %d\n",ans,be>n?be-n:be,en>n?en-n:en); } int main(){ int t; scanf("%d",&t); while(t-- >0){ input(); computing(); } return 0; }
rmq算法,超時,郁悶中
?
?
#include <iostream> #include <cmath> #include <cstdio> using namespace std; const int maxn=300005*2; int maxsum[maxn][20],minsum[maxn][20],flog[maxn],d[maxn],sum[maxn],n,k; void ini(){ int r=2,cnt=0; for(int i=1;i<maxn;i++){ if(i<r) flog[i]=cnt; else{ flog[i]=++cnt; r=r<<1; } } } void input(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&d[i]); d[i+n]=d[i]; } } void getrmq(){ for(int i=1;i<=2*n;i++){ sum[i]=sum[i-1]+d[i]; maxsum[i][0]=sum[i]; minsum[i][0]=sum[i]; } for(int j=1;j<=flog[2*n];j++) for(int i=1;i<=2*n;i++){ if(i+(1<<j)-1<=2*n){ maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]); minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]); } } } void computing(){ getrmq(); int ans=-(1<<30),be=1,en=1,l,r,x,tmp; for(int i=1;i<=n;i++){ l=i,r=i-1+k,x=flog[r-l+1]; tmp=max(maxsum[l][x],maxsum[r-(1<<x)+1][x]); if(tmp-sum[i-1]>ans){ ans=tmp-sum[i-1]; be=i; } } for(int i=be;i<=be+k-1;i++){ if(sum[i]-sum[be-1]==ans){ en=i; break; } } printf("%d %d %d\n",ans,be>n?be-n:be,en>n?en-n:en); } int main(){ ini(); int t; scanf("%d",&t); while(t-- >0){ input(); computing(); } return 0; }
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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