30号下午有道难题第一题分析

今天下午的有道难题参加了,3题做了2道,而且全部没AC,第一个是WA,第二个是TLE。很郁闷,感觉自己还有好多要加强,这里废话也不多说,下午和群里朋友讨论了下,k发了一个很强悍的代码,个人感觉很好,但是不好理解,这里把代码和分析贴出来和大家一起学习。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 #include <iostream>
#include <stdio.h>
#include <cstring>
#include<algorithm>
using namespace std;
 
int main()
{
	int n,k,tem,i,ans;
	char c;
 
	scanf("%d",&n);
	scanf("%c",&c);
	getchar();//这个很精辟的空格 用了2个接收字符
	for(i=0;i<n;i++)
	{
		ans=0;
		tem=0;
 
		while(scanf("%c",&c)&&c!='\n')
		{
			tem=tem&0x0f;       //取上一次c转换后的后四位
			tem=tem<<8;         //左移8位,使上次的后四位移至12~8位,这里大家可以考虑为什么是4位?
			tem=tem|c;          //与c抑或
			if((tem&0x00000fc0)==0x00000840)
				ans++;
			if((tem&0x000003f0)==0x00000210)
				ans++;
			if((tem&0x000000fc)==0x00000084)
				ans++;
			if((tem&0x0000003f)==0x00000021)
				ans++;
		}
		printf("%d\n",ans);
	}
 
	return 0;
}
/*这里给大家说下为什么是4位:
因为上一字符最后可能为da,这样此次字符开头是o就可以了*/
/*
上面的fc是11111100, 3f是00111111,
tem&0x00000fc0的作用就是去掉不相干的位,这个地方不好说,大家好好理解下.
0840 = 0000 1000 0100 0000
0210 = 0000 0010 0001 0000
0084 = 0000 0000 1000 0100
0021 = 0000 0000 0010 0001
大家看出来了吧。
里面全部包括了100001,这就是dao.

以下是题目:
描述
‘道’是中国古代哲学的重要范畴。用以说明世界的本原、本体、规律或原理。在不同的哲学体系中,其涵义有所不同。老子所写的《道德经》是关于‘道’的经典著作。

道的原始涵义指道路、坦途,以后逐渐发展为道理,用以表达事物的规律性。这一变化经历了相当长的历史过程。《易经》中有“复自道,何其咎”(《小畜》),“履道坦坦”(《履》),“反复其道,七日来复”(《复》),都为道路之义。

《尚书•洪范》中说:“无有作好,遵王之道;无有作恶,遵王之路。无偏无党,王道荡荡;无党无偏,王道平平;无反无侧,王道正直”。这里的道,已经有正确的政令、规范和法度的意思,说明“道”的概念已向抽象化发展。

—- 节选自有道词典(http://dict.youdao.com)

  Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。它把每三个8Bit的字节转换为四个6Bit的字节(3*8 = 4*6 = 24),然后把6Bit再添两位高位0,组成四个8Bit的字节,也就是说,转换后的字符串理论上将要比原来的长1/3。

有道的工程师闲暇之余,将Base64编码改成了Base4编码,即把每个8Bit的字节转换成4个2Bit的字节,然后以4个字符来代替。编码和字符的对应方案如下:
00 —- a
01 —- o
10 —- d
11 —- 空格
这样,编码后的字符串就只会含有字符‘d’,’a’,’o’和空格。

例如字符y ,其ASCII码是121,对应的二进制串是01111001,这样分成 01 11 10 01四块后,用Base4编码后的字符串为”o do”。

有道的工程师很好奇,按照这种编码方式,编码后的字符串中含有多少个完整的dao呢?一个完整的dao由连续的‘d’,’a’,’o’三个字符组成。
输入
第一行有一个正整数n,代表接下来有n个待编码的原串。(1 <= n <= 10) 接下来有n行,每行有一个长度不超过106的原串,原串中的字符可能为ASCII码中除换行符以外的任意可见字符。 输出 共有n行,每行为一个整数k, 表示输入数据中对应的原串用Base4编码后含有多少个完整的dao。 样例输入 2 www.youdao.com dict.youdao.com 样例输出 1 1 提示 Java时限是标准时限的3倍,而且对于每个输入文件都有100ms的额外IO时间

有道难题

对自己深刻的反思,今天,是有道难题第一场资格赛,晚上吃饭忘了时间,去的时候已经过了一个小时了,还好明天还有一场,于是就准备把今天的三题作为练手,可是,看了第一名的朋友,37分钟搞定,我震惊了,这才是实力,而我呢?每天以为自己学到了,其实全都在搞论坛网站上去了,其实网站和论坛只是个学习交流的地方,真正的还是自己的实力啊!

我决定了,从明天开始,绝对按计划进行。

上午看英文版《TC PL》,下午学习算法和做题,尽量做三题吧。晚上学习课本,这学期我可不像再悲剧了,而且最后一段时间还有毛邓呢,所以现在就要抓紧好好学习!

不要在丢失了真正的自我,以后顶多上午11点后,下午5点至6点,晚上9点后搞网站!

该开始努力了!

论ACM与泡妞(ZZ)

abstract :本文从各个方面讨论了泡妞与做题之间的相似之处与不同点,尽量的站在一个公平的角度阐述这一问题,所得的研究成果填补了国内外的理论空白。 –

泡了一个好妞就好像做了一道难题一样快感都是相同的。 –

首先这两项活动都需要耗费大量的精力,一般都是20岁左右的时候,最有激情最有精力参加这两项活动。所以参加acm的同时大多都是适婚男青年,主要人群两者基本相同。 –

就像普通人一辈子泡妞的日子不过三五年,acm也有五年参赛的限制。 –

假如你泡妞泡的特有成就,比如搞定了张梓琳。就好比参加了final一样,顶多你再参加一次,就是你最多搞俩世界小姐,太多了剩下的哥们怎么办呐。所以妞泡多了要低调,final机会也要留给后人呐。 –

从具体操作上看要想成为大牛,你就要不断的做题比如在pku上切到第一版。这里也有一个惊人的事实!大家都知道poj是国内最火的oj,几乎就是广大acmer在网上的家园。而当我们把题看作妞的时候,就不难理解为什么一个韩国高中生能在高手如云的poj稳坐第一把交椅了,哎,韩流啊… –

一个题目的status就好比反映了一个妞的感情历史,她的现任男友自然就是status排名第一的好汉了。假如把泡到一个妞花费的金钱和精力比作是所耗内存和cpu时间。就不难理解为什么大家都愿意孜孜不倦的优化自己的程序来抢夺status的第一把交椅了。花最少的精力和金钱来泡妞,才是高手追求的境界。这也就解释了为什么有时候pku出一点bug,偶尔把内存搞成了负的,大家就纷纷兴奋的截图留念,因为这是偶然才能达到的神一样的泡妞境界,让妞倒贴你钱,也就是传说中的神龙见首不见尾的软饭高手。 –

有些妞是名妞,比如说pku2520,当年曾经拒绝过教主的追求长达1个多月,这是何等的荣耀啊。以至于教主把到了之后都禁不住说:”爽死了!!! 720683 LouTianCheng 2520 Accepted 912K12734MS G++ 2.86K 2005-09-16 14:55:41.0″[1] –

近年来最著名的题目推荐列表莫过于zhucheng大牛的分类列表了[2],这个列表在妞中的地位就好比超女一样。本来是淹没在题海中的一道平凡的题目,通过了zhucheng大牛的层层筛选,进得榜单便是一夜之间声望猛增,成为通向“万花丛中过,片叶不占身”境界的一条必经之路。 –

除了如日中天的poj,还有一个著名的泡妞社区也是为大家所熟知的,著名的topcoder。 –

此社区经常举办有奖泡妞比赛,四海高手蜂拥而致。国内一统江湖的教主在这里才有互为一时瑜亮的人物,罗刹泡妞高手peter。 –

这个比赛的一大特点就是妞泡的不但要又快又准。在第一轮的纷纷大献殷勤之后,还不一定能抱得美人归,第二轮就是各位好汉互挖墙角了,横刀夺爱之举屡有发生,而一轮群雄混战后,天下格局又是沧海桑田。 –

下面我们主要来讨论下各种各样类型的妞,世间妞虽千千万,但总体上还是能分出个类别: –

有些妞就像模拟题告诉你她想要的是什么,你只要能一步一步做到就终有泡到的一天。但如果她非要求你摘颗星星下来,那只能说这是一个很变态的模拟题了… –

搜索题型妞:有些妞喜欢找个知己当男友老是幻想自己跟男友能“佛祖拈花,迦叶微笑”,那你就得有深度优先的精神,照死里揣摩她的心思,碰上个没事喜欢伤春悲秋的500年前跟黛玉姐姐是一家的愣是给你整个stackoverflow了,你搞不好还得手动递归;有些妞喜欢自己装嫩,泡起来就跟养个女儿一样,你得照顾的面面俱到,好比是个广搜妞;有些妞对你若即若离,没事抛个媚眼,你来了却又不能让你中宫直进,猜一步是一步,显然是个A*妞;有些妞喜欢跟你循序渐进,不必说就是个迭代加深的妞了; –

图论妞:这种妞是很普遍的一部分类型,泡之前先得搞理论准备。先看个[CLRS]Graph theory那一章算是入个门,我们就拿其中最典型的网络流妞来说吧。泡这样的妞,那是一项工程,你要打通她周围的关系,先请她寝室的人吃个饭啊,那好比是找增广路。要是有钱咱就整个预留推进,管它代价多少先往里砸,效率就相当的高,尤其是人际关系比较广的,明显优于一个个请吃饭的。当她周围的人都说你好的时候,恭喜你,终于找到最大流了,要是想少花钱还能泡到妞,那就上最小费用流吧。(这个是受以前看到的某个文章的启发,可是找不到出处了…) –

至于DP妞啊,线段树妞啊就不一一列举了,大家发挥想象吧。 –

大代码量的题目好比身材丰满,环肥燕瘦的妞。少不了上下其手。而骨感美女大多以青春感性取胜,那就要你做法推陈出新,想人所未想,匪夷所思的讨她欢心。 –

比赛的时候第一个过掉某个题目,感觉就跟泡到了virgin一样。西方中世纪某些地方贵族享有平民妻子的初夜权,而区域赛中大部分首先过题的都是成名已久的牛人。而假如某个题目有一个弱队先过了,大家便会一窝蜂的抢上前去水之。就好比哪天你发现住你对门寝室的哥们在操场跟本校的校花激情热吻一样,而这哥们前天还问你A罩杯大还是B罩杯大。估计你会立刻判定这个校花泡到的难度很低。便来名花虽有主,我来松松土呀。或者是这个校花脑子突然进水了,才被对门的哥们搞定,就好比题是难题但是数据挫了,被大家纷纷暴力过了一样,带给出题人惨痛的伤害呀… –

每年正统的泡妞大赛就是各个区域赛及final,而google code jam跟ASTAR也是不可小视。code jam时候各个早就是名人堂的人物都会出现,象张一飞大牛啊。 –

astar则是以工程性的妞出名,要到电话不难,吃个饭也尚能接受,可要是真想让这个妞对你死心塌地。那就比一般的妞麻烦多了。 –

oi比赛就是贯彻了小平爷爷的指示“泡妞,要从娃娃抓起”。 –

红颜易老,妞只能泡两三年,比赛也只有青春的这么一段岁月可以投入。结婚了就好比退役了,找了个好老婆就能举案齐眉,好比final归来衣锦还乡一样。而要是只有一个区域赛的honorable mention,就只能留下一个萧瑟的背影了。 –

本文纯属娱乐,如有冒犯敬请原谅。 –

祝所有看我这篇文章的兄弟们都能找到自己的真爱,在ACM/ICPC的旅程中收获 meanning of your life.-

八卦D.E.Knuth

传说 Knuth 写书写文章的第一稿都是用铅笔写的。
很多人不明白他为什么不用键盘。
其实原因是这样,Knuth 曾经参加过一个训练小秘的学习班,
练习打字每分钟 80 个词以上。

到了后来,他发现他打字的速度大大高于他思考的速度,
所以如果他用键盘,就会出现很多停顿。
所以他决定用铅笔,这样可以与读者的思考速度保持一致。

Knuth 作为一个计算机科学家,
为什么放下他所有的工作10年,
专心研究排版美学,创造 TeX 系统。
这是很奇怪的一件事情。

其实原因是这样。真正完美的数学排版应该是用金属活字进行的。
但是自从70年代以来,真正懂得这项技术的人都死光了。
新的排版机器,很不幸的都被计算机操纵了 (想想 Matrix )

虽然当时计算机能够排出一些简单的报纸,杂志,
但是它们不能很好的处理数学公式。

Knuth 想写出一个小玩艺儿能够在不同的计算机上制造漂亮的数学公式,
于是 TeX (读作 Tech(nology) 的前半部分) 就诞生了。

很多人都对 TeX 断行的算法感到满意,
其实只有 Knuth 觉得担心。

他设计 TeX 的时候听说有一本书叫做 Aesthetic Measures,
作者是美国 No.1 数学家 George David Birkhoff。
是说怎样用数学公式来衡量“美”。

他查阅了7个Harvard图书馆,其中有一个图书馆有一个拷贝,
但是却被人借走了。无奈,跑到 MIT 去借。

还好,借到了。后来他就在 TeX 里加入了一个变量叫做 badness,
用来衡量一行文字的美感 adness 越小这行文字就越美。

但是与 Birkhoff 不同,Knuth 对这个公式没有多少信心。
也许是因为谦虚。

Knuth 的书都是自己用 TeX 排版的,但是却不都是自己设计的。

传说 Knuth 和 Graham, Patashnik 合作写 Concrete Mathmatics 的时候
请了一位有名的图书版面设计家为他们设计好了书的尺寸,字体大小,标题样式,
后来 Hermann Zapf 专门设计了一种数学字体叫做 Euler,
自此,数学家 Euler 的灵魂浮游于 CM 当中……

另外一个图书设计家告诉 Knuth 一种格式数学公式的办法,
就是不把数学居中,而是只相对正文缩进一定距离。

大家都知道 1974 年图灵奖授予 Knuth
主要是因为他写了一部巨著叫做
The Art of Computer Programming

但是不幸的是,很多人不能理解,甚至不相信
他为这部书起了这么一个不“科学”的名字。

后来很多人的著作里出现这样的文献引用:

“The Act of Computer Programming, Donald Knuth.”

Knuth 是个喜欢自夸的人,这是毫无疑问的。
在他出版 The Art of Computer Programming 之前就已经有这种苗头了。

还没有出版的时候,在一次会议上,有个人知道他的这种性格,
就说:“我猜你正在写的这本书的书名肯定是 ‘An Introduction to Don Knuth’。”

Knuth 回答说:“正好相反。我要以你的名字来命名它。”

原来这个人的名字叫 “Art Evans”.

Knuth 是Caltech数学系博士毕业的
但是他常常说:“我戴着一顶计算机科学家的帽子,而不是一顶数学家的帽子。”

这说明他似乎对数学家有某些看法。
在他看来数学家只知道“What is it”,
而他还知道 “How to do it”.
这就是他认为的数学与计算机科学的区别。

Knuth 回到 Stanford 时,学校让他自己给自己一个头衔

他就选了一个
Professor Emeritus of The Art of Computer Programming

他其实觉得“计算机科学”不是科学。
虽然大家很希望计算机编程变成科学,这是某ACM刊物提出的忠旨。
但是 Knuth 觉得奇怪为什么大家这么喜欢科学,
以致于他们瞬间把程序设计变成了科学,方法就是叫它“计算机科学”。

— Just call it “Computer Science”

在他眼里,计算机科学其实仍然是门艺术。

在 Knuth 的眼里,科学与艺术有什么区别呢?
艺术是人创造的,而科学不是。
艺术永远是可以无止境的提高的,而科学不是。
艺术需要天赋才能掌握,而科学不需要,按部就班就行。

所以,The … ART … of Computer Programming!

Knuth 的 The Art … ft,这么长……以后简称TAOCP吧

…… 开始写的也不那么好。

传说有一天 Bob Floyd 给 Knuth 一封信,开门见山就说:
“Don, 请不要用那么多感叹号!”信的结尾至少打了五个概叹号。

看了之后,Knuth 发现 TAOCP 里竟然平均每页有两个感叹号!!

有人说 Knuth 写完三卷 taocp 就去研究 TeX,其实是因为害怕写第四卷。
很多人早就希望他放下 TeX,继续写书。
Knuth 说:“一个人要把事情做的完美,只有当他跟上帝的意图保持和谐,
现在上帝要我去写第四卷了。”

Knuth 很推崇随机算法。
他批改作业时,一般都是翻到随机一页,仔细看那一页,
之后就对学生的作业有了一个概貌,其它的部分就看的不那么仔细了。

Knuth 看书的时候首先看第316页,如果书很短就看第100页。
仔细看那一页。之后他就可以说那本书好不好。
据说这样做出判断的正确率很高。

不知道是否有很多人跟他学,看316和100.
以后写书要注意把第316页或者100页写好呀!

继续八卦

你们知道 Knuth 发明了一种程序设计方法叫做 Literate Programming (文学编程)
把程序当成文学作品来写。这样可以创造永恒的作品,
甚至几十年后还有人用它作为茶余饭后的读物。

他为什么要发明这个东西。原因有2:

1. 他想让一个程序员(也许是他自己)在某一天拿到普利策奖。
2. 他想让提出“Structured Programming”(结构化程序)的那些家伙
在写“非文学程序”的时候,就像他当年写“非结构化程序”
的时候一样觉得自己有罪。

他的“文学编程”思想最早是在英国 Computer Journal 发表的。
当人问他为什么不在美国发表。
他说,美国人没文化,他们不能理解这个东西。

Knuth 喜欢在他的作品里用 “we” 作为主语,
虽然很多时候文章是他一个人写的。

有人认为使用被动语态好。但是 Knuth 认为不应该大量使用被动语态。
“用 We 可以减少被动语态带来的麻烦。‘we’是指你和你的读者。”
那么怎么称呼作者?答案是: the authors, the first author, 或者直接用名字。

但是他确实反对使用 “I”,除非你是身名显赫,
人人尊敬的君王式人物,否则最好不要在论文里用 “I”。

在你描述你的程序时,喜欢说 “we insert the element in the heap”
还是 “it inserts the element in the heap” ?
Knuth 总是喜欢用 “we”。显然他已经融于算法的动作之中了。

虽然他不喜欢论文里用 “I”, 但是他喜欢让他的程序自称 “I”.

看这里:

This is TeX, Version 3.14159 (Web2C 7.3.7x)
! I can’t find file `kkkk.tex’.
kkkk.tex

Please type another input file name:

有很多人跟着他学,把这种称呼顽皮的发挥到极致:

Welcome to Scheme 48 0.57 (made by wy on 日 11月 24 13:20:27 CST 2002).
Copyright (c) 1993-2001 by Richard Kelsey and Jonathan Rees.
Please report bugs to [email]scheme-48-bugs@martigny.ai.mit.edu[/email].
Type ,? (comma question-mark) for help.
> (define (sq x) (* x
x))

; no values returned
>
Exit Scheme 48 (y/n)?
I’ll only ask another 100 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 99 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 98 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 97 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 96 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 95 times.
Exit Scheme 48 (y/n)?
I’ll only ask another 94 times.
Exit Scheme 48 (y/n)?
……

Knuth 有一次布置了一个作业,要求在两个星期以内做出一个
用于控制时代广场那种 8×256 像素的阵列显示屏幕的系统,
并且写出一个用户手册。这个用户手册必须让不懂电脑的人也能看懂。

作业交上来以后 Knuth 把文档拿给他夫人(Jill Knuth)看,
结果发现 Jill 对文档里的 “Menu” 和 “Scrolling” 这样的单词都摸不着头脑,
更不要说 “left-indented”, “exit”, …

Knuth 曾经在 American Mathematical Monthly 发表过一篇
叫做 “The Toilet Paper Problem” 的论文,
据说是一个研究怎样合理使用厕纸的算法。

现在收录于 Selected Papers on Analysis of Algorithms, p.111
可惜清华图书馆没有。谁找到copy我一份。呵呵。

这篇论文投到 Monthly 时,在节标题使用了大量“粪便学”词汇。
编辑警告 Knuth 说,笑话在我们这里是危险的,请你三思!

不得已啊,Knuth 后来把小节标题里的那种词改掉了。
可是他很不想改文章的标题。
怎么办呢?
他给编辑一封信说,我已经以这个标题做过两次演讲,
这个主题已经被广泛的采用和讨论……云云。

最后编辑回信说:“你的厕纸被接受了!”

无语ing。。。。。。

====================================
P.S. 附录:增加这篇论文的信息:

Stanford 计算机科学系楼里的厕纸架上可以并排放两筒厕纸。
人上厕所时有可能从两个中的一个取纸。

两个卷筒不一样大的时候,喜欢从大的那筒拿纸的人叫做 big-chooser
喜欢从小的那筒拿纸的人叫做 little-chooser。

如果两筒大小差不多,一般人都会从离自己最近的那筒取纸。

厕纸用完的时候一般由janitor(门口老大爷?)提供新的纸。
如果一边的用完了,那就换掉那一边,
如果两边同时用完,那么有人就有麻烦了……(我怀疑Knuth遇到了那么一次)

我没仔细看完。
Knuth 似乎在计算那种两筒同时用完的窘境出现的概率……

论文原文的一个拷贝在:
http://learn.tsinghua.edu.cn/homepage/015450/doc/toiletPaperProblem.pdf

似乎不能用了

比较复杂的数学…… 有兴趣的可以看看。

另外,Don Norman 在这里有一些新设计的厕纸筒可以避免这种情况发生:

http://www.jnd.org/dn.mss/ToiletPaperAlgorithms.html

连不上国外网,不知道还能不能看到

看来 Knuth 是在白费工夫。应该授予 IgNobel 或者 IgFields

Knuth 和 Graham 他们合写的 Concrete Mathematics 本来
不会做的那么花哨的。

结果后来他们专门为那本书设计了字体,页面样式,
所有习题都给出了出处。几乎所有页面都至少有一个涂鸦,
连《爱利丝漫游奇境记》都被列入参考文献……

这是怎么回事呢?原因就是 Knuth 在写书期间去看了一部电影:
“白雪公主与七个小矮人”。

看完之后 Knuth 感叹道:
难以置信,这样完美的艺术品竟然可以在1937年完成。
我一定要把我的书做成一个艺术品,而且要在三个月之内完成!

结果他说到做到了。

百练 OJ 2766 最大子矩阵

//ID: 百练 OJ 2766 最大子矩阵
//题目地址: http://poj.grids.cn/problem/2766
//My Name: Tanky_Woo
//My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习
//Website Link: http://www.cpply.com/
//My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛
//BBS Link:http://www.cppleyuan.com/
//My Blog:www.wutianqi.com
//豆瓣小组:http://www.douban.com/group/cppleyuan/
//QQ:17611904
//QQ群:C++奋斗乐园①群:19333724(满) ②群:23840480 (满)③群:17314377 ④群:23829384
//转载请写上本帖链接 www.cpply.com|www.cppleyuan.com|www.wutianqi.com
//及名称”Tanky Woo与ACM一起走过的日子”和“C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 //方法一
/*思想很经典,即利用求数组最长子段的函数。现在考虑如何利用这个函数,从第一行开始,到N行,遍历每种情况:
第i行到第j行上下元素相加,压缩成一个数组*/
#include <iostream>
using namespace std;
 
int N;
int aMatrix[101][101];
int aLine[101];
#define INF -10000000
 
int maxSubMatrix(int *line);
 
int main()
{
	//freopen("input_2766.txt", "r", stdin);
	int maxSum = INF;
	int i, j, k , h;
	scanf("%d", &N);
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			scanf("%d", &aMatrix[i][j]);
	for(k = 0; k < N; k++)
	{
		for(h = k; h < N; h++)
		{
			for(j = 0; j < N; j++)
				aLine[j] += aMatrix[h][j];
			int sum = maxSubMatrix(aLine);
			if(sum > maxSum)
				maxSum = sum;
		}
		memset(aLine, 0, sizeof(aLine));
 
 
	}
	printf("%d\n", maxSum);
	return 0;
}
 
 
 
int maxSubMatrix(int *line)  //求数组的最长子段
{
	int i;
	int b = line[0], sum = line[0];
	for(i = 1; i < N; i++)
	{
		if(sum > 0)     //这个地方应该是判断b是否大于0,我先写成了sum,结果测试了几组数据是对的,但其实是错的!
			b += line[i];
		else
			b = line[i];
 
		if(b > sum)
			sum = b;
	}
 
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 //方法二:
/*这题应该算用了DP吧。*/
 
#include<stdio.h>
#include<memory.h>
int a[102][102];
int b[102][102];
 
int main(){
 //1.两个坐标点就确定了一个矩阵,然后枚举所有的矩阵(直接枚举会超时)
 //2.先计算(0,0)(i.j)确定的矩阵的值b[i][j]
 //3.枚举所有矩阵,利用b[i][j]分割计算 
 int n,ma=0;
 scanf("%d",&n);
 for(int i=0;i<=n+1;i++){//设置边框
  a[0][i]=0;
  a[n+1][i]=0;
  a[i][0]=0;
  a[i][n+1]=0;
 }
 
 for(int i=1;i<=n;i++)//输入
  for(int j=1;j<=n;j++){
   scanf("%d",&a[i][j]);
   if(a[i][j]>ma)ma=a[i][j];
  }
 
 
 for(int i=0;i<=n;i++)        //求b[i][j]
  for(int j=0;j<=n;j++)
   for(int p=0;p<=i;p++)
    for(int q=0;q<=j;q++)
     b[i][j]+=a[p][q];
 int sum=0;
 for(int i=1;i<=n;i++)    //枚举矩阵
  for(int j=1;j<=n;j++)
   for(int p=i;p<=n;p++)
    for(int q=j;q<=n;q++){
     sum=0;
     sum=b[p][q]-b[p][j-1]-b[i-1][q]+b[i-1][j-1];
     if(sum>ma)ma=sum;
 
    }
 printf("%d",ma);
 
}