題意：
? ? ? 給你一個(gè)數(shù)字組成的環(huán)，要求在里面找到一個(gè)最大的子序列，使得和最大，要求：
（1）子序列長(zhǎng)度不能超過(guò)k
（2）如果子序列和相同要起點(diǎn)最小的
（3）如果起點(diǎn)相同要長(zhǎng)度最小的


思路：
? ? ? 首先環(huán)我們可以把序列放大一倍，然后Ans = maxx(sum[j] - sum[i]); ?其中j>i，j-i>=k,sum[i]是前綴和，對(duì)于每一個(gè)j我們只要找到前面最小的那個(gè)sum[i]就行了，這樣就變成了一個(gè)比較裸的一個(gè)單調(diào)隊(duì)列的題目，求最小我們的隊(duì)列可以使遞增的，每次從隊(duì)尾進(jìn)，把比當(dāng)前大的出隊(duì)（不是大于等于，是大的，這樣保證同樣和的時(shí)候前綴最小），隊(duì)頭的話只要把距離當(dāng)前值距離大于k的出隊(duì)就行了，還有就是記住一點(diǎn)，每次都是先詢問(wèn)在進(jìn)隊(duì)，那么在詢問(wèn)之前一定要判斷下隊(duì)頭的id是否過(guò)期，也就是隊(duì)頭是否要出先隊(duì)列，這個(gè)地方大一了wa了一發(fā)。?




#include<stdio.h>
#include<string.h>


#define N 200000 + 10


typedef struct
{
? ?int id ,num;
}NODE;


NODE Q[N];
int num[N];
int tou ,wei ,k;


void insert(int id ,int num)
{
? ?for(int i = wei ;i > tou ;i --)
? ?if(Q[i].num > num) wei --;
? ?else break;
? ?Q[++wei].id = id;
? ?Q[wei].num = num;
? ?for(int i = tou + 1 ;i <= wei ;i ++)
? ?if(id - Q[i].id > k) ?tou ++;
? ?else break;
}


int main ()
{
? ?int t ,n ,j ,i;
? ?int Ansa ,Ansb ,Ansc;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d %d" ,&n ,&k);
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%d" ,&num[i]);
? ? ? ? ?num[i+n] = num[i];
? ? ? }
? ? ? Ansc = - 1000000000;
? ? ? tou = wei = 0;
? ? ? int sum = 0;
? ? ? Q[++wei].num = 0;
? ? ? Q[wei].id = 0;
? ? ? num[0] = 0;
? ? ? for(i = 1 ;i <= n + n ;i ++)
? ? ? {
? ? ? ? ?sum += num[i];?
? ? ? ? ?while(i - Q[tou+1].id > k)
? ? ? ? ?tou ++; ?
? ? ? ? ?int now = sum - Q[tou+1].num;
? ? ? ? ?if(now > Ansc)
? ? ? ? ?Ansc = now ,Ansa = Q[tou+1].id + 1,Ansb = i; ??
? ? ? ? ?insert(i ,sum);
? ? ? }
? ? ? if(Ansb > n) Ansb -= n;
? ? ? printf("%d %d %d\n" ,Ansc ,Ansa ,Ansb);
? ?}
? ?return 0;
}
? ? ??
? ? ??
? ? ??
? ?
? ?
? ?
? ?






? ? ??
? ?

總結(jié)

以上是生活随笔為你收集整理的hdu3415单调队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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