鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=3415

意甲冠軍：環(huán)。要找出當(dāng)中9長(zhǎng)度小于等于K的和最大的子段。

思路：不能採(cǎi)用最暴力的枚舉。題目的數(shù)據(jù)量是10^5，O(N^2)的枚舉回去超時(shí)。本題採(cǎi)用的非常巧妙的DP做法，是用單調(diào)隊(duì)列優(yōu)化的DP。

運(yùn)用的是STL的deque，從i:1~a找到以當(dāng)中以i為尾的符合條件的子段。并將i本身放入雙向隊(duì)列。全部i從隊(duì)列后放入，保證了隊(duì)列的單調(diào)性。

代碼：

      #include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define maxn 100005*2
#define maxm
#define INF 0x7fffffff
typedef long long ll;
using namespace std;
int num[maxn],sum[maxn];
int main()
{
    int tot;
    scanf("%d",&tot);
    while(tot--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        scanf("%d",&num[1]);
        sum[1]=num[1];
        for(int i=2;i<=a;i++)
        {
            scanf("%d",&num[i]);
            sum[i]=sum[i-1]+num[i];
        }
        for(int i=a+1;i<a+b;i++)
        sum[i]=sum[i-1]+num[i-a];
        deque < int > dd;
        int ans=-INF,head=-1,tail=-1;
        for(int i=1;i<a+b;i++)
        {
            while(!dd.empty()&&sum[i-1]<sum[dd.back()])
            dd.pop_back();
            while(!dd.empty()&&i>dd.front()+b)
            dd.pop_front();
            dd.push_back(i-1);
            if(sum[i]-sum[dd.front()]>ans)
            {
                ans=sum[i]-sum[dd.front()];
                head=dd.front()+1;
                tail=i;
            }
        }
        if(head>a)
        head-=a;
        if(tail>a)
        tail-=a;
        printf("%d %d %d\n",ans,head,tail);
    }
    return 0;
}