题意分析

首先这道题不可以使用简单的贪心来做

根据\(DP\) 我们令\(dp[i]\)表示当前到了\(i\)一共做了\(dp[i]\)次合并

\(pre[i]\)表示当前合并到了\(i\)后序列末尾的数

那么\[dp[i]=min\{dp[j]+i-j,sum[i]-sum[j]≥pre[j]\}\]

可惜是\(O(n^2)\)的

我们考虑由于是\(dp[i]=dp[j]+val_i\)的形式

所以我们可以使用单调队列优化

\[sum[i]≥sum[j]+pre[j]\]

根据贪心法则我们希望恰好满足

所以我们维护一个递增的单调队列

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 500008#define IL inline#define M 1008611#define D double#define ull unsigned long long#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/int n,head,tail;int num[N],que[N],dp[N];ll sum[N],pre[N];int main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout); read(n); for(R int i=1;i<=n;++i) read(num[i]); for(R int i=1;i<=n;++i) sum[i]=sum[i-1]+1ll*num[i]; head=0;tail=1; for(R int i=1;i<=n;++i) { while(head+1
                    
                     =sum[que[head+1]]+pre[que[head+1]]) ++head; pre[i]=sum[i]-sum[que[head]];dp[i]=i-que[head]-1+dp[que[head]]; while(head