好久没写了，单调队列。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int dp[2000001],p[2000001],sum[2000001]; 6 int que[2000001]; 7 int main() 8 { 9     int n,m,i,str,end;10     scanf("%d%d",&n,&m);11     for(i = 1;i <= n;i ++)12     {13         scanf("%d",&p[i]);14         sum[i] = sum[i-1] + p[i];15     }16     dp[0] = m;17     str = end = 0;18     for(i = 1;i <= n;i ++)19     {20         while(str < end&&dp[i-1] - sum[i-1] > dp[que[end-1]]-sum[que[end-1]])21         end --;22         que[end++] = i-1;23         dp[i] = dp[que[str]]-i*100 + sum[i]-sum[que[str]];24         while(str < end&&dp[que[str]]-(i+1)*100 < 0)25         str ++;26     }27     printf("%d\n",dp[n]);28     return 0;29 }