亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ 3415 Max Sum of Max-K-sub-sequence (線

系統 2025 0

?

?

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

Problem Description
Given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].
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.
?

?

Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.?
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).
?

?

Output
For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.
?

?

Sample Input
4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3 -1 2 -6 5 -5 6 6 6 -1 -1 -1 -1 -1 -1
?

?

Sample Output
7 1 3 7 1 3 7 6 2 -1 1 1
?

?

Author
shǎ崽@HDU
?

?

Source
?

?

Recommend
lcy
?
?

?

題目大意: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;

}
    


?


?

?

POJ 3415 Max Sum of Max-K-sub-sequence (線段樹+dp思想)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 色综合视频在线观看 | 精品一区二区三区18 | 国产精品揄拍一区二区久久 | 欧美理论在线观看 | 亚洲区精品久久一区二区三区 | 久久久久久久久免费影院 | 最新狠狠色狠狠色综合 | 久久精品国产免费中文 | 久草免费新视频 | 国产精品公开免费视频 | 青青草免费在线视频 | 国产一区二区三区欧美 | 日本一区毛片免费观看 | 国产成人aa视频在线观看 | 亚洲欧美一区二区久久香蕉 | 亚洲欧美另类在线 | 欧美成人免费观看久久 | 精品国产九九 | 欧美色网| 亚洲香蕉网综合久久 | 国产精品视频偷伦精品视频 | 久久综合五月天 | 久久久99精品 | 国产青草视频免费观看97 | 毛片一级在线观看 | 久久久精品麻豆 | 国产精品午夜波多野结衣性色 | 国产成人久久精品麻豆二区 | 日本精品久久久中文字幕 | 精品福利在线视频 | 毛片录像| 天天射天天做 | 久草经典视频 | 精品偷拍模特露出丝袜在线 | 久久久精品国产免费观看同学 | 国产一级毛片国语版 | 女人18免费毛片视频 | 夜夜夜夜夜夜夜猛噜噜噜噜噜噜 | 香蕉免费一级视频在线观看 | 免费不卡中文字幕在线 | 日日摸夜夜摸狠狠摸日日碰夜夜做 |