pascal求大神1206:趣味彩票时间限制:1Sec内存限制:128MB提交:150解决:50[提交][状态][讨论版]题目描述现今，社会上流行着各种各样的福利彩票，彩票已经融入到了人们的日常生活之中

Question

pascal求大神
1206: 趣味彩票
时间限制: 1 Sec 内存限制: 128 MB
提交: 150 解决: 50
[提交][状态][讨论版]
题目描述
现今，社会上流行着各种各样的福利彩票，彩票已经融入到了人们的日常生活之中。彩票之所以能吸引那么多的人们，玩法多是一大原因。
小明五一放假和爸爸一起到广州游玩，发现了一种趣味彩票，玩法新颖，有别于传统的彩票形式。规则是这样的：
1．彩票中心每期随机产生N行M列整数（整数范围为-100~100）；
2．彩民选取1~10000之间的任意一个整数P，P即为选取的彩票号码；
3．彩票中心产生特等奖号码的规则如下：
(1) 从随机产生的N*M个数中选取M个数，每列必须选取一个，这样有NM种选法。
在已选的M个数中，再选取若干个连续的数，如果这些数的和是NM种选法中所有连续序列里最大的，则称之为“幸运号码序列”。
(2)计算“幸运号码序列”的和，得到特等奖号码。
彩票中心请小明来编这个程序----计算特等奖号码，可是小明学习编程不久，你能帮助小明完成这个艰巨的任务吗？
输入
输入文件共有N+1行：
第1行有两个数：N(1<=N<=100)和M(1<=M<=10001)，中间用空格隔开；
第2行至第N+1行：每行为随机产生的M个整数。
输出
输出文件共有2行：
第1行：特等奖号码；
第2行：“幸运号码序列”中数的个数，（如果有相同的和，输出其中最短的序列个数）；
样例输入 Copy
3 5-50 -47 36 -30 -2317 -19 -34 -13 -8-42 -3 -43 34 -45
样例输出 Copy
844
提示
数据规模
20%的数据： N<=1000 40%的数据： N<=5000
100%的数据： N<=10001
来源
[提交][状态][讨论版]

Answer 1

由于输入没有加上回车，所以根据我的判断，数据应该是这样的：
输入：3 5
-50 -47 36 -30 -23
17 -19 -34 -13 -8
-42 -3 -43 34 -45
输出：84
4
我根据这个数据写了一个程序，思路如下：
首先，因为是在每一列中寻找一个数，组成有M个数的一串数，同时使得这一串数的和最大。那么显然我们每次都取出这一行中的最大数，这样贪心地取数显然不会得到更差的方案。然后我们再对这一串数做一遍O(N)连续子序列最大值即可。当然，如果你不会O(N)的算法，也可以用O(N^2)的前缀和优化连续子序列最大值。当然，这不是重点，网上的题解还是很多的。详见程序：
var
i,j,n,m,x,t,ans,max,head,tail:longint;//ans表示最大值的序列长度，也就是“幸运号码序列”中数的个数，max为最大值，也就是特等奖号码，head为当前序列的头指针，tail为尾指针
a:array[0..101,0..1001] of longint;//表示这O(MN)个数
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;//读入
for i:=1 to m do//枚举M行
begin
x:=a[1,i];
for j:=2 to n do
if a[j,i]>x then
x:=a[j,i];//x表示第i行的最大值，此处为更新最大值
tail:=i;//尾指针后移一位
if t>=0 then t:=t+x else//t≥0，显然直接累加不会得到更差的方案
begin
head:=i;//t＜0，那么将t赋为x，不会得到更差的方案，当然，头指针要赋为i
t:=x;
end;
if t>max then//刷新最大值
begin
max:=t;
ans:=tail-head+1;//更新最大值，同时长度一起更新
end else
if t=max then//与最大值相等
if tail-head+1 ans:=tail-head+1;//更新最大值下的最小长度
end;
writeln(max);
writeln(ans);
end.