一本通 1.1 练习 2【数列分段】

首先对于一个序列，从$a[1$ ~ $l]$都符合最佳序列，假设对于第$l$ $+$ $1$个数，它放到从$l$ $+$ $1$ ~ $r$的区间是一种最优的方法，并且它也可以放在从$1$ ~ $l$ $+$ $1$这里，那么根据贪心，它放到$1$ ~ $l$ $+$ $1$的序列中是合法的，而且也是一种最优方案。

因此，这道题只需要贪心：能将当前数往左放就往左放。

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, m, a[100010], ans, cnt;
 5 int main()
 6 {
 7     scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
 8     for(int i = 1; i <= n; ++i)
 9     {
10         cnt += a[i];
11         if(cnt + a[i + 1] > m) ++ans, cnt = 0;
12     }
13     printf("%d", ans + 1);//这个是加上最后一个区间 
14     return 0;
15 }