UC知道求一条ACM算法程序，能提交成功的加送100分。
来源：百度知道 编辑：UC知道 时间：2024/05/03 04:15:21
在http://acm.pku.edu.cn/JudgeOnline/problem?id=3017这里提交
问题：
Cut the Sequence
Time Limit:2000MS Memory Limit:131072K
Total Submit:532 Accepted:84
Description
Given an integer sequence { an } 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 int
问题：
Cut the Sequence
Time Limit:2000MS Memory Limit:131072K
Total Submit:532 Accepted:84
Description
Given an integer sequence { an } 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 int
想到了几条原则：
1、大数尽量分到一个块儿中
2、块数量尽量少。
具体算法没有想出来
感觉应该从 sequence 中最大的数，往有大数的方向进行“搜索”……
补充：
此题需要设计比较好的数据结构，以降低计算复杂度。
提供几个测试用例吧（#表示切割线的位置）：
假设M=17
2 2 2 9 1 # 8 2 1 output: 9+8
此用例比较直接，从最大数开始“搜索”，即可得到划分
2 2 2 9 # 3 1 8 2 1 output: 9+8
此用例就需要全局考虑了，如果单单往大数的方向（9往3的方向）搜索，会划分成下面这样：
2 # 2 2 9 3 1 # 8 2 1 这样因为多了一个片断，不是最优划分。
2 # 2 2 9 3 1 # 8 3 3 output:2+9+8
---------------------------
另外，此题也可以换一个思路，虽然题目要求的是切分序列，但是反过来想：将单个的数字合并 也是一个思路。
本人水平有限，以上仅供参考，祝LZ好运。
不懂 高人来解答吧 顺便学习下
Input