POJ 3017 单调队列dp - c++编程基础

Cut the Sequence

Time Limit: 2000MS		Memory Limit: 131072K
Total Submissions: 8764		Accepted: 2576

Description

Given an integer sequence { a_n } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.

Input

The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.

Output

Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output 1.

Sample Input

8 17
2 2 2 8 1 8 2 1

Sample Output

把序列分成若干部分，每一部分的和不超过m，求每一部分里最大值和的最小值。

开始没啥思路，研究了半天，感觉单调队列dp非常的精妙，先mark一下，后面慢慢理解吧。

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/13 1:35:25
File Name :C.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; ll que[100100],a[100100],dp[100100]; int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); //dp 方程：f[i]=f[j]+max(x[j+1],x[j+2],...,x[i]),其中j
                
                 m)flag=0; } if(!flag){ puts("-1");continue; } ll front=0,rear=0,p=1; dp[1]=a[1];que[rear++]=1; ll sum=a[1]; for(ll i=2;i<=n;i++){ sum+=a[i]; while(sum>m)sum-=a[p++];//区间和小于等于m while(front
                 
                  =a[que[rear-1]])rear--;//单调严格递减队列 que[rear++]=i; while(que[front]