数列求和2
Time Limit: 1000MS Memory limit: 65536K

题目描述
给出一个数列 S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). 我们定义 sum(i, j) = S i +S i+1+ ... + S j (1 ≤ i ≤ j ≤ n).
现在给你一个整数 m (n>=m > 0), 你的任务是找出m对 i，j 使 sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) 最大化 (i x ≤ i y ≤ j x 或 i x ≤ j y ≤ j x 是不允许的).
结果仅输出sum(i x, j x)的最大累加和(1 ≤ x ≤ m) 就行了.

输入
包含多组数据，每组数据占一行，前两个整数是m和n，后面紧跟着是n个整数S 1, S 2, S 3 ... S n.

输出
输出所描述的结果，每一组的结果占一行

示例输入
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

示例输出
6
8

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

疯狂的小金
Time Limit: 1000MS Memory limit: 65536K

题目描述
自从听说小白和小黑的友谊的小船翻了以后，小金很是开心，就和小白建立了小船，但是现在小金看到天上的n只小鸟，就萌生了一个疯狂的想法，他决定带着小白去打鸟，所以小金去商店买装备--->箭，现在他知道每只鸟的防御力，和每一只箭的攻击力和价值。如果箭的攻击力小于鸟的防御了，小鸟是不会被打下来的。最为奇葩的是每种箭只有一只，小金想将小鸟都打下来，如果不能那么小金和小白的小船又要翻啦。当然小金的资金最近比较的紧张，所以他想花费最小的钱。

输入
多组输入，每组第一行输入两个数n,m(1<=n,m<=50000)，表示小鸟的数量和箭的数量。接下来的一行的n个数表示每一个小鸟的防御力，接下来的m行，每行两个数，表示箭的攻击力v价值w,(1<=v,w<=100000).

输出
如果小金不能将所有的小鸟射下来，输出"No Solution"。否则输出最小的花费。

示例输入
3 3
1 2 3
2 1
3 2
4 3

示例输出
6

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

硬币问题
Time Limit: 1000ms Memory limit: 65536K

题目描述
芳芳有N（1<=N<=1000)个硬币，这些硬币排成一列，有正有反。我们定义这样一种操作，把[l,r]区间上的硬币都翻过来(1<=l<=r<=N).
芳芳想知道经过一次这样的操作后，最多有多少正面朝上的。
1代表正面，0代表反面。
比如：0 1 0 三个数，把区间1-3进行操作，数字就会变成1 0 1 正面向上的个数为2.

输入
本题有多组测试数据，每组数据有两行.
第一行包含一个数字N. 第二行有N个数字，1表示正面，0表示反面.

输出
每组数据输出一行.

示例输入
4
1 0 0 1

示例输出
4

提示

来源
第六届山东理工ACM网络编程擂台赛决赛

皮卡丘的梦想
Time Limit: 1000ms Memory limit: 65536K

题目描述
一天，一只住在 501 的皮卡丘决定发奋学习，成为像 LeiQ 一样的巨巨，于是他向镇上的贤者金桔请教如何才能进化成一只雷丘。
金桔告诉他需要进化石才能进化，并给了他一个地图，地图上有 n 个小镇，并且标注了每个小镇上可收集的进化石。
但是皮卡丘拿到地图就蒙圈了，他可不知道自己到底需要哪种进化石，而且由于经费有限，他只能去某几个相邻的小镇，所以他机智地找到了善于编程的你，询问你这些镇上可收集的进化石有哪些，然后再自己决定行程。

输入
首先输入一个整数 T (1 <= T <= 10)，代表有 T 组数据。
每组数据的第一行输入一个整数 n (1 <= n <= 100000)，代表有 n 个小镇。
接下来的 n 行表示第 1 个到第 n 个的小镇的信息。每行先输入一个整数 m (0 <= m <= 30)，代表这个小镇上进化石的种类数，紧接着输入 m 个整数，代表进化石的种类编号（编号从 1 开始，不超过 30）。
之后的一行输入一个整数 q (1 <= q <= 25000)，代表皮卡丘有 q 次询问。 接下来的 q 行每行输入两个整数 l, r (1 <= l <= r <= n)，表示他想询问从第 l 个到第 r 个小镇上可收集的进化石有哪几种。

输出
对于每组输入，首先输出一行 "Case T:"，表示当前是第几组数据。
接下来对于每一次询问，按编号升序输出所有可收集的进化石。如果没有进化石可收集，则输出一个小豪的百分号 "%"（不要问我为什么，出题就是这么任性）。

示例输入
1
3
2 3 10
3 1 2 4
0
3
1 2
2 3
3 3

示例输出
Case 1:
1 2 3 4 10
1 2 4
%

提示

来源
bLue

小明的花费预算
Time Limit: 1000ms Memory limit: 65536K

题目描述
小明终于找到一份工作了，但是老板是个比较奇怪的人，他并不是按照每月每月的这样发工资，他觉得你想什么时候来取都可以，取的是前边连续几个月中没有取的工资，而小明恰好是一个花钱比较大手大脚的人，所以他希望每次取得钱正好够接下来的n个月的花费。
所以让你把这n个月分成正好m组。每个组至少包含一个月，每组之中的月份必须是连续的，请你为他分组，使得分得的组中最大的总花费最小。

输入
第一行是两个整数，n（1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n)
接下来的n行是连续n个月的花费，第i+1行是第i个月的花费。

输出
输出满足最大的总花费最小的那个组的总花费。

示例输入
5 3
3
2
9
4
1

示例输出
9

提示
将5个月分为3组，第一组(3,2),第二组(9),第三组(4,1)，第二组的总花费最大为9，若按其他的方式分，花费最大的那一组的总花费将>=9.

来源
lwn