POJ3017 解题报告

好题！ 单调队列优化DP。 定义 $f_i$ 为分配到第 $i$ 个数，所求的最优解。 我们可以使用单调队列维护 $sum\le m$ 范围内的最大值，然后遍历边界刷新 $f$ 数组。 另外设立一个 $f2$ 指针来维护边界。

/*
* @ Author: Xiaohuba
* @ Usage: OI Problem
* @ Language: C++
*/
#include<bits/stdc++.h>
using namespace std;

/* ---File Head Begin--- */
namespace Xiaohuba_File_Head
{
  //def
  #define ll long long
  #define lll __int128
  #define pii pair<int,int>
  #define mkp make_pair
  #define vi vector<int>
  #define vs vector<string>
  #define viit vector<int>::iterator
  #define pb push_back
  #define il inline 
  #define pch putchar
  #define gch getchar
  #define Endl putchar('\n')
  #define Space putchar(' ')
  #define For(x,st,ed) for(int x=(st),END=(ed);x<=END;++x)
  #define ForDown(x,st,ed) for(int x=(st),END=(ed);x>=END;--x)
  #define sq(x) (x*x)
  #define Set(a,b) memset(a,b,sizeof(a))
  #define Cpy(a,b) memcpy(a,b,sizeof(a))
  #define PRIME_MOD 100000007ll
  #ifdef ONLINE_JUDGE
    #define log2 __lg
    #define gcd __gcd
  #endif
  //io
  template <typename T>
  il void read(T & tmp){ tmp=0;char c=getchar();bool flg=0;while(!isdigit(c)) flg=c=='-',c=getchar();while(isdigit(c)) tmp=(tmp<<3)+(tmp<<1)+c-'0',c=getchar();if(flg) tmp*=-1; }
  template <typename T, typename... Args>
  il void read(T &tmp, Args &...tmps){ read(tmp);read(tmps...); }
  template <typename T>
  il void __write(const T &x){ if(x==0) return;__write(x/10);putchar(x%10+'0'); }
  template <typename T>
  il void write(const T &x){ if(x==0) putchar('0');if(x<0) putchar('-');__write((x<0 ? -x : x)); }
  template <typename T>
  il void write_with_space(const T &x){ write(x);Space; }
  template <typename T>
  il void write_with_endl(const T &x){ write(x);Endl; }
  template <typename T, typename... Args>
  il void write_with_space(const T &x, const Args &...y){ write_with_space(x);write_with_space(y...); }
  il void __getline(istream & istr, string & str){ getline(istr,str);if(*(str.end()-1)=='\r') str.erase(str.end()-1); } 
  #define getline __getline
};
using namespace Xiaohuba_File_Head;
/* ---File Head End--- */

#define int ll
int n,m;
int a[100001];
int q[100001],front,tail;
int f2;
int f[100001];
int sum[100001];
bool flg=0;

signed main()
{
  read(n,m);
  For(i,1,n) read(a[i]),sum[i]=sum[i-1]+a[i],flg|=a[i]>m;
  if(flg) return !printf("-1");
  front=f2=1,tail=0;
  For(i,1,n)
  {
    while(front<=tail && sum[i]-sum[q[front]-1]>m) ++front;
    while(front<=tail && a[q[tail]]<=a[i]) --tail;
    while(sum[i]-sum[f2-1]>m) ++f2;
    cout<<f2<<' '<<q[front]<<endl;
    q[++tail]=i;f[i]=f[f2-1]+a[q[front]];
    For(j,front+1,tail)
    {
      f[i]=min(f[i],f[q[j-1]]+a[q[j]]);
    }
  }
  cout<<f[n];
  return 0;
}