POJ 3017 单调队列dp-白红宇

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 172 2 2 8 1 8 2 1

Sample Output

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

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

代码：

/* ***********************************************Author :_rabbitCreated Time :2014/5/13 1:35:25File 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; ll n,m; while(~scanf("%lld%lld",&n,&m)){ bool flag=1; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); if(a[i]>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]

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5141354.html，如需转载请自行联系原作者