【题目描述】
小猪在小学中认识了很多的字，终于会写一点作文了。某天小猪买了一张方格稿纸来写作文，n行m列，形状如下所示：
上图中n=m=5。
某天小猪的邻居小小猪来小猪家玩，用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色，如下图所示。
小猪不能责怪小小猪。作文写不成了，他觉得很无聊，就开始数里面有多少魔幻方阵。
如果稿纸中一个k×k的正方形区域满足以下两个条件，那么它就是魔幻方阵：
1．黑白格子的数量差不能超过1；
2．k不能小于2。
上图染色后的方格稿纸共有9个魔幻方阵（6个2×2的魔幻方阵，3个3×3的魔幻方阵），现在请你帮小猪求出他被染色的稿纸里面有多少个魔幻方阵。
【输入】
输入文件paint.in中的第一行有二个正整数n和m（互相之间以一个空格分隔），表示稿纸共有n行m列。
接下来n行，每行有m个0或1的整数（互相之间以一个空格分隔），代表每个格子的颜色。如果这个数是1则为黑色，是0则为白色。
【输出】
输出文件paint.out中仅有一行，该行只有一个整数，表示稿纸中魔幻方阵的个数。
【样例输入】
5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1
【样例输出】
9
【数据规模】
50%的数据，1≤n≤10，1≤m≤10；
75%的数据，1≤n≤180，1≤m≤180；
100%的数据，1≤n≤300，1≤m≤300。
3. 教室外的风景 (scene)
【题目描述】
小猪上初中了，初中真好啊，有很多自修课哦。很多同学喜欢在自修课时到教室外面去，说是到老师那问问题J。
学校规定，自修课到教室外去的每个同学都必须做好登记，每次进出教室的登记是以一对整数a和b来描述的，表示某一个同学在时刻a时到教室外面，在时刻b以后回到教室内。也就是说在时刻a至时刻b的这段时间中，这个登记的同学一直在教室外面。
校长想知道最多有多少同学在同一时刻都在教室外面，但同学们进进出出教室的记载实在很乱，于是校长请参加信息学兴趣小组的小猪来统计。
【输入】
输入文件scene.in中的第一行只有一个整数n，表示共有n个同学进出教室的记载。
接下来n行，每行二个整数a和b，表示有一个同学在第a时刻出了教室，他在第b时刻后回到教室。
【输出】
输出文件scene.out中仅有一行，该行只有一个整数，表示最多有多少同学在同一时刻都在教室外面。
【样例输入】
4
2 6
8 9
1 5
1 2
【样例输出】
3
【样例说明】
第一个同学在时刻2到教室外面,在时刻6后回到教室;
第二个同学在时刻8到教室外面,在时刻9后回到教室;
第三个同学在时刻1到教室外面,在时刻5后回到教室;
第四个同学在时刻1到教室外面,在时刻2后回到教室;
因此在时刻2时，最多有3个同学（第一个、第三个和第四个）在教室外面。
【数据规模】
50%的数据中，1≤n≤1000；每个同学进出教室的时刻a和b满足：1≤a≤b≤1000；
100%的数据中，1≤n≤100000，1≤a≤b≤100000000。
4. 瓶子涂色 (bottle)
【题目描述】
小猪上小学的时候，一度对颜色非常感兴趣，虽然他的美术非常糟糕。
有一次他喝完n瓶饮料把透明的瓶子排成一排，想把这些饮料瓶子都涂上颜色。他觉得如果所有相邻的两个瓶子颜色都不一样的话会比较有趣。
他现在只有红色(Red)、绿色(Green)和蓝色(Blue)这三种颜料。由于瓶子的大小和表面材质不同，在不同的瓶子上涂不同的颜色需要的花费都不一样。小猪统计了一下，把第i个瓶子染成红色需要Ri元钱，染成绿色需要Gi元钱，染成蓝色需要Bi元钱。
现在请你帮他计算出要使相邻两个瓶子的颜色都不一样，他至少需要多少花费。
【输入】
输入文件bottle.in中的第一行只有一个整数n，表示共有n只瓶子。
第二行有n个正整数（以一个空格分隔）,第i个数Ri表示把第i个瓶子染成红色需要Ri元钱。
第三行有n个正整数（以一个空格分隔）,第i个数Gi表示把第i个瓶子染成绿色需要Gi元钱。
第四行有n个正整数（以一个空格分隔）,第i个数Bi表示把第i个瓶子染成蓝色需要Bi元钱。
【输出】
输出文件bottle.out中仅有一行，该行只有一个整数，表示最小花费。
【样例输入】
5
1 3 1 2 2
1 2 3 4 3
4 2 1 5 3
【样例输出】
9
【数据规模】
30%的数据中，1≤n≤10；
70%的数据中，1≤n≤30；
100%的数据中，1≤n≤100000，1≤Ri, Gi, Bi≤100。
我也参加了 100多吧
最后一题用动归啊[/quote]
说的具体点。动规我也知道。数据模型如何构建。
2.
范围只有300，考虑到一共只有 O(N^3) 个正方形，所以考虑枚举所有正方形，在 O(1) 时间判断每个正方形是否合法。
将输入中所有黑色格子标记为 1，所有白色格子标记为 -1。则一个正方形中黑白格子数量差不超过 1，等价于这个正方形内所有数字的和的绝对值不超过 1。
于是转化为求和问题。
比较简单的处理方法是用部分和优化。记 Sum(i, j) 表示 (1, 1) 到 (i, j) 这个区域所有数字的和（规定 Sum(i, 0) = Sum(0, j) = 0）。
则区域 (x0, y0) - (x1, y1) 的和为 Sum(x1, y1) - Sum(x0 - 1, y1) - Sum(x1, y0 - 1) + Sum(x0 - 1, y0 - 1)
3.
做离散化，把所有同学离开教室和回到教室的时间点拆开并标记、排序。之后按照时间顺序枚举时间点模拟同学进出，更新最大值即可。时间复杂度 O(N + 排序时间)
4.
动态规划。设 F(i, C) 为前 i 只瓶子，第 i 个染成 C (=0,1,2) 色的最小花费。
转移方程：
F(i, C) = min{F(i - 1, C0)} + Cost(i, C) （其中 C0 不等于 C，Cost(i, C) 表示第 i 个瓶子染成 C 色的花费）
边界：
F(0, C) = 0
最后输出 max{F(N, 0), F(N, 1), F(N, 2)}。
时间复杂度 O(N)。
写一点我的想法吧：
2.
范围只有300，考虑到一共只有 O(N^3) 个正方形，所以考虑枚举所有正方形，在 O(1) 时间判断每个正方形是否合法。
将输入中所有黑色格子标记为 1，所有白色格子标记为 -1。则一个正方形中黑白格子数量差不超过 1，等价于这个正方形内所有数字的和的绝对值不超过 1。
于是转化为求和问题。
比较简单的处理方法是用部分和优化。记 Sum(i, j) 表示 (1, 1) 到 (i, j) 这个区域所有数字的和（规定 Sum(i, 0) = Sum(0, j) = 0）。
则区域 (x0, y0) - (x1, y1) 的和为 Sum(x1, y1) - Sum(x0 - 1, y1) - Sum(x1, y0 - 1) + Sum(x0 - 1, y0 - 1)
3.
做离散化，把所有同学离开教室和回到教室的时间点拆开并标记、排序。之后按照时间顺序枚举时间点模拟同学进出，更新最大值即可。时间复杂度 O(N + 排序时间)
4.
动态规划。设 F(i, C) 为前 i 只瓶子，第 i 个染成 C (=0,1,2) 色的最小花费。
转移方程：
F(i, C) = min{F(i - 1, C0)} + Cost(i, C) （其中 C0 不等于 C，Cost(i, C) 表示第 i 个瓶子染成 C 色的花费）
边界：
F(0, C) = 0
最后输出 max{F(N, 0), F(N, 1), F(N, 2)}。
时间复杂度 O(N)。
[/quote]
谢谢兄台。先按兄台思路，尝试一下，待解决后分数送上。
谢谢兄台。先按兄台思路，尝试一下，待解决后分数送上。[/quote]再次感谢兄台，按照兄台给的思路，题目已做出，分数附上
但想要4个AC,就难了.
我的结果(比赛)
2.AAAAATTTTTAAAAAAAAAA(N^3也有27000000了,是C++和FP的差距?)
3.AAAAABBBBB(崩溃)
4.AAAWWWWWWAAAAAAAAAAA(动归一个地方打错了)
再次感谢兄台，按照兄台给的思路，题目已做出，分数附上[/quote]