代码
比这篇新的文章:
butter.cpp
比这篇旧的文章: range.pas
作者: xpycc, 点击196次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: range.pas
range.right.cpp
语言: C++, 标签: 无 2008/08/22发布 3个月前更新作者: xpycc, 点击196次, 评论(0), 收藏者(0)
C++语言: range.right.cpp
01 /*
02 ID:xpycc1
03 PROG:range
04 LANG:C++
05 */
06
07 #include <fstream>
08 using namespace std;
09
10 ifstream fin("range.in");
11 ofstream fout("range.out");
12
13 typedef unsigned pasint;
14
15 const pasint maxn = 250;
16
17 pasint n;
18 char fieldpr;
19 pasint sq[maxn+1], // 最大面积
20 sqpr,
21 numsq[maxn+1]; // 所求答案
22
23 pasint min3(pasint a ,pasint b ,pasint c) {
24 if ((a <= b) && (a <= c))
25 return a;
26 else
27 return (b <= c) ? b : c;
28 }
29
30 int main() {
31 pasint r, c, i, tmp;
32
33 fin >> n;
34
35 for (r = 1; r <= n; r++) {
36 sqpr = 0;
37 sq[0] = 0;
38 for (c = 1; c <= n; c++) {
39 fin >> fieldpr;
40 if (!(fieldpr - '0')) {
41 sqpr = sq[c];
42 sq[c] = 0;
43 continue;
44 }
45
46 /*
47 * 精华部分：状态转移
48 * sq[c-1]西边 sq[c]北边 的最大矩形大小
49 * 由循环可知sqpr代表着原来的sq[c-1]，也就是西北边的最大矩形大小
50 * 寻找3个方向中最小的最大矩形大小
51 * 那么这个位置的最大矩形大小就是：
52 * 这个最小矩形大小加1的结果
53 */
54 tmp = 1 + min3(sq[c-1], sqpr, sq[c]);
55 sqpr = sq[c];
56 sq[c] = tmp;
57
58 // 增加矩形个数
59 if (sq[c] >= 2)
60 numsq[ sq[c] ]++;
61 /*
62 * for(i=sq[c]-1;i>=2;--i)
63 * numsq[ i ]++;
64 * 不要忘记比自己小的矩形个数也在同时增加
65 * 注：这段程序的效果完全可以由程序段1替代
66 */
67 }
68 }
69
70 // 程序段1：
71 // 最后的精彩，取代上面的程序段，使复杂度降为2次
72 for (i = n-1; i >= 2; i--)
73 numsq[i] += numsq[i+1];
74
75 for (i = 2; i <= n && numsq[i]; i++)
76 fout << i << " " << numsq[i] << endl;
77
78 return 0;
79 }
02 ID:xpycc1
03 PROG:range
04 LANG:C++
05 */
06
07 #include <fstream>
08 using namespace std;
09
10 ifstream fin("range.in");
11 ofstream fout("range.out");
12
13 typedef unsigned pasint;
14
15 const pasint maxn = 250;
16
17 pasint n;
18 char fieldpr;
19 pasint sq[maxn+1], // 最大面积
20 sqpr,
21 numsq[maxn+1]; // 所求答案
22
23 pasint min3(pasint a ,pasint b ,pasint c) {
24 if ((a <= b) && (a <= c))
25 return a;
26 else
27 return (b <= c) ? b : c;
28 }
29
30 int main() {
31 pasint r, c, i, tmp;
32
33 fin >> n;
34
35 for (r = 1; r <= n; r++) {
36 sqpr = 0;
37 sq[0] = 0;
38 for (c = 1; c <= n; c++) {
39 fin >> fieldpr;
40 if (!(fieldpr - '0')) {
41 sqpr = sq[c];
42 sq[c] = 0;
43 continue;
44 }
45
46 /*
47 * 精华部分：状态转移
48 * sq[c-1]西边 sq[c]北边 的最大矩形大小
49 * 由循环可知sqpr代表着原来的sq[c-1]，也就是西北边的最大矩形大小
50 * 寻找3个方向中最小的最大矩形大小
51 * 那么这个位置的最大矩形大小就是：
52 * 这个最小矩形大小加1的结果
53 */
54 tmp = 1 + min3(sq[c-1], sqpr, sq[c]);
55 sqpr = sq[c];
56 sq[c] = tmp;
57
58 // 增加矩形个数
59 if (sq[c] >= 2)
60 numsq[ sq[c] ]++;
61 /*
62 * for(i=sq[c]-1;i>=2;--i)
63 * numsq[ i ]++;
64 * 不要忘记比自己小的矩形个数也在同时增加
65 * 注：这段程序的效果完全可以由程序段1替代
66 */
67 }
68 }
69
70 // 程序段1：
71 // 最后的精彩，取代上面的程序段，使复杂度降为2次
72 for (i = n-1; i >= 2; i--)
73 numsq[i] += numsq[i+1];
74
75 for (i = 2; i <= n && numsq[i]; i++)
76 fout << i << " " << numsq[i] << endl;
77
78 return 0;
79 }
所有评论，共0条：( 我也来说两句)