月度归档：2010年02月

三取方格数

发表回复

【问题描述】
背景 Background
JerryZhou同学经常改编习题给自己做。

这天，他又改编了一题。。。。。

【描述 Description】
设有N*N的方格图，我们将其中的某些方格填入正整数，

而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

【输入格式 Input Format】

第一行:N (4<=N<=20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0 【输出格式 Output Format】 一行，表示最大的总和。 【样例输入 Sample Input】 4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 2 4 样例输出 Sample Output 39 注释 Hint 多进程DP 算法分析 可以用网络流来做 由于没做二取方格数；我一开始用一般DP；DP一次则把走过的路删去；3次DP； 只对了一组；看了题解后知道了我的算法虽然保证了3次DP的最优；但并不代表全局最优；是有反例的...... 其实可以用压缩数组的方法..因为每一阶段都只与上一阶段有关..滚动滚动数组..循环利用..不断再生..节约环保..{好像扯远了...-_-#}..不过节约时间起见..其实不用滚动数组也可以以0ms过掉.. 　　做这条题时很深刻地感受得到..这条题是斜着划分阶段的..太伟大了啦..而且由于每一阶段中..横坐标与纵坐标有一种莫名的内在关系..所以为数组节约了不少维..{不过就算不节约..N<=20..也应该不会超..}.. 用sum[k,x,y,z]表示当走到第K步时,且三人横坐标分别为X,Y,Z时..所取数的最大值..由于每一个人都可以由2个方向推来..所以一共有2^3=8种状态.. sum[k,x,y,x]=max(sum[k,x,y,z],sum[k-1,x+f[i,1],y+f[i,2],z+f[i,3]]) 且由于第K步只能到达横坐标<=min(k,n)的点..所以其实循环时可以节约节约.. 注意:每一格只能取一次..数组的大小.. 【代码】 

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
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
int min(int a, int b)
{
 
       if (a < b)
              return a;
       else
              return b;
 
}
 
int f[41][21][21][21], a[21][21];
 
int main()
{
 
       int n, i , j, k, x1, x2, x3, temp, s1, s2, s3;
       scanf("%d", &n);
 
       for (i = 1; i <= n; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);
 
       }
 
       memset(f, 0, sizeof(f));
       f[1][1][1][1] = a[1][1];
 
       for (k = 2; k <= n + n -1; k++)
       {
              for (x1 = 1; x1 <= min(k, n); x1++)
              {
 
                     for (x2 = 1; x2 <= min(k, n); x2++)
                     {
                            for (x3 = 1; x3 <= min(k, n); x3++)
                            {
                                   temp = a[k - x1 + 1][x1] + a[k - x2 + 1][x2] + a[k - x3 + 1][x3];
 
                                   if (x1 == x2)
                                          temp -= a[k - x1 + 1][x1];
 
                                   if (x1 == x3)
                                          temp -= a[k - x1 + 1][x1];
 
                                   if (x2 == x3)
                                          temp -= a[k - x2 + 1][x2];
 
                                   if (x1 == x2 && x1 == x3)
                                          temp += a[k - x1 + 1][x1];
 
                                   for (s1 = -1; s1 <= 0; s1++)
                                   {
                                          for (s2 = -1; s2 <= 0; s2++)
                                          {
                                                 for (s3 = -1; s3 <= 0; s3++)
                                                 {
                                                        f[k][x1][x2][x3] = max(f[k][x1][x2][x3], f[k - 1][x1 + s1][x2 + s2][x3 + s3] + temp);
                                                 }
                                          }
                                   }
                            }
                     }
              }
       }
 
       printf("%d\n", f[n + n - 1][n][n][n]);
       return 0;
}

PHP源码阅读笔记六：stream_get_wrappers函数

发表回复

PHP源码阅读笔记stream_get_wrappers函数
stream_get_wrappers

(PHP 5)
stream_get_wrappers — 返回注册的数据流列表
Description

array stream_get_wrappers ( void )

Returns an indexed array containing the name of all stream wrappers available on the running system.

在某次其他函数的实现过程中需要知道url_stream_wrappers_hash变量的来源，
从而发现此函数也是从url_stream_wrappers_hash变量直接读取数据，
于是有了对于此函数和url_stream_wrappers_hash变量的跟踪过程。
首先在standard文件夹下的streamsfuncs.c文件中包含了此扩展的实现
其路径如下：

1
2
3
4

==>PHP_FUNCTION(stream_get_wrappers)        //    streamsfuncs.c 548行
==>#define php_stream_get_url_stream_wrappers_hash() _php_stream_get_url_stream_wrappers_hash(TSRMLS_C)    //    php_stream.h    552行
==>PHPAPI HashTable *_php_stream_get_url_stream_wrappers_hash(TSRMLS_D)        //    streams/streams.c    58行
==>static HashTable url_stream_wrappers_hash;    //    全局静态变量，

从此函数的代码中我们可以看出它是直接遍历php_stream_get_url_stream_wrappers_hash()函数的返回值，生成一个字符串数组
php_stream_get_url_stream_wrappers_hash()函数

而函数直接调用全局变量中的数据，此变量初始化和注册过程跟踪如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

url_stream_wrappers_hash初始化位置：
==>int php_init_stream_wrappers(int module_number TSRMLS_DC)    //    streams.c     1395行  初始化数据流
引用位置：
==> if (php_init_stream_wrappers(module_number TSRMLS_CC) == FAILURE)     //    main.c 1765行，初始化，注册数据流
 
添加默认注册的流程如下：
==> zend_startup_modules(TSRMLS_C);    //    main.c 1843行，添加注册数据流
==>zend_hash_apply(&module_registry, (apply_func_t)zend_startup_module_ex TSRMLS_CC);    //    zend_API.c    1519行
==>ZEND_API int zend_startup_module_ex(zend_module_entry *module TSRMLS_DC)    //    zend_API.c 1424行    
==>if (module->module_startup_func) {    //    zend_API.c    1470行
==>PHP_MINIT_FUNCTION(basic)    //    basic_functions.c     3973行
==> php_register_url_stream_wrapper("php", &php_stream_php_wrapper TSRMLS_CC);
 php_register_url_stream_wrapper("file", &php_plain_files_wrapper TSRMLS_CC);
 php_register_url_stream_wrapper("data", &php_stream_rfc2397_wrapper TSRMLS_CC);
#ifndef PHP_CURL_URL_WRAPPERS
 php_register_url_stream_wrapper("http", &php_stream_http_wrapper TSRMLS_CC);
 php_register_url_stream_wrapper("ftp", &php_stream_ftp_wrapper TSRMLS_CC);
#endif 
     //     basic_functions.c    4073行，添加过程
==>php_register_url_stream_wrapper    //    main/streams/streams.c    1450行

此次跟踪的时间跨度为一周，也算是经历几多磨难。但是最后总算是弄清楚其来源。