作者归档：admin

矩阵连乘

【代码】

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

#include <stdio.h> 
#include <string.h> 
#define N 100 
int m[N][N]; //m[i][j]表示从第i个矩阵连乘到第j个矩阵的最小计算次数 
int s[N][N]; //第i个矩阵连乘到第j个矩阵时在何处断开，用于构造最优解 
int p[N];    //表示矩阵i为p[i-1]×p[i] 
 
void MatrixChain(int n) 
{ 
       int i,j,k,t,r; 
       for(i=1;i<=n;i++) 
              m[i][i]=0; 
       for(r=2;r<=n;r++) 
       { 
              for(i=1;i<=n-r+1;i++) 
              { 
                     j=i+r-1; 
                     m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 
                     s[i][j]=i; 
                     for(k=i+1;k<j;k++) 
                     { 
                            t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 
                            if(t<m[i][j]) 
                            { 
                                   m[i][j]=t; 
                                   s[i][j]=k; 
                            } 
                     } 
              } 
       } 
} 
 
void TraceBack(int i,int j) 
{ 
       if(i==j) return; 
       TraceBack(i,s[i][j]); 
       TraceBack(s[i][j]+1,j); 
       printf("Multiply A%d,%d and A%d,%dn",i,s[i][j],s[i][j]+1,j);                                               
 
} 
 
int main() 
 
{ 
       int i,n; 
       memset(m,0,sizeof(m)); 
       scanf("%d",&n); 
       for(i=0;i<=n;i++) 
              scanf("%d",&p[i]); 
       MatrixChain(n); 
       printf("%dn",m[1][n]); 
       TraceBack(1,n); 
       return 0; 
}

ubuntu系统安装和lamp安装

ubuntu系统安装和lamp安装
前些日子一直在XP和windows7下徘徊，觉得windows7很帅，但是有些慢，特别是装了apache后运行PHP巨慢
所以重装了系统，在周末给自己装了XP和utunbu双系统。总共整了两天，才算是系统装好，这还不包括那些特效之类的东东
第一步，下载官方网站的iso文件，http://www.ubuntu.org.cn/getubuntu/download/
第二步，可以选择硬盘安装，也可以选择光盘安装，
硬盘安装，出于节省的目的，我开始选择的从硬盘安装，在google狂搜后找到相关的说明，使用CRUB等，参照http://forum.ubuntu.org.cn/viewtopic.php?f=77&t=217161
依据这样做我可以看到安装的界面，并且到了第三步和第四步之间，即选择了键盘布局之后，就一直停在那，不动了，我以为安装失败了在  http://hi.baidu.com/serial_story/blog/item/90ddb8946900f617d31b70ca.html有说是可能硬盘文件太多导致的。所以我选择从光盘安装，结果失败
光盘安装，  在这里我选择使用nero烧录，光盘录制好后，重启，从光盘启动安装，与从硬盘安装一样，到了扫描硬盘后就无法进行下去了，结果失败
使用wubi安装，但是在进行在快要完成的时候，它又不动了，怎么办呢？google吧，网上有人说是语言，是网络的问题，于是我把网络关掉，语言换成English,结果仍然是失败，与硬盘安装
如出一辙。但是在一次次尝试过程中，有一次使用wubi时，没有把光盘拿出来，结果它装好了，而且还跑得不错。RP啊

安装好ubuntu后，咱得搞点开发环境了，于是lamp就提上了日程，一开始我使用源码安装，那个痛苦啊，不好说，主要是以前没有用过linux,所以。。。
痛定思痛后，改使用apt-get安装

buntu下安装 apache+php+mysql

sudo apt-get install mysql-server mysql-client

sudo apt-get install apache2

sudo apt-get install php5 libapache2-mod-php5

sudo /etc/init.d/apache2 restart

在地址栏中输入http://loalhost/
如果可以看到显示

It works!

则表示apache安装成功！

在/var/www/目录下新建一个PHP文件，在里面写入

＜?PHP
phppath();
?&gt;

如果有显示PHP相关信息，则表示php和apache安装整合成功，

如果要把mysql的datadir换一个地方，请移步http://forum.ubuntu.org.cn/viewtopic.php?f=44&t=172891的第6楼

附：

sudo /etc/init.d/apache2 restart （重启 apache）

sudo /etc/init.d/mysql restart (重启mysql)

sudo gedit /etc/php5/apache2/php.ini （配置 php.ini）

sudo gedit /etc/apache2/apache2.conf （配置 apache2.conf）

/var/www/（主目录位置）

另：
ubuntu发行版本的主配置文件是：

apache2.conf

在apache2.conf引用到了以下文件：

# 包含动态模块的配置:

Include /etc/apache2/mods-enabled/*.load

Include /etc/apache2/mods-enabled/*.conf

# 包含用户自己的配置:

Include /etc/apache2/httpd.conf

# 包含端口监听的配置:

Include /etc/apache2/ports.conf

# 包含一般性的配置语句片断:

Include /etc/apache2/conf.d/

# 包含虚拟主机的配置指令:

Include /etc/apache2/sites-enabled/

修改httpd.conf

增加以下内容：

ServerName 127.0.0.1:80

晴天小猪历险记之Hill

在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结……
　　不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草。于是，晴天小猪的传奇故事便由此展开……

【描述 Description】
　　这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂，由于小小猪的病情，晴天小猪想找一条需时最少的路到达山顶，但现在它一头雾水，所以向你求助。
　　山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1<=T<=100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。 　　晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。 【输入格式 Input Format】 　　第一行有一个数n（2<=n<=1000），表示山的高度。 　　从第二行至第n+1行，第i+1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。 【输出格式 Output Format】 　　一个数，即晴天小猪所需要的最短时间。 【算法描述】 f[i,j]=min{f[i-1,j-1],f[i-1,j],f[i,j-1],f[i,j+1]}+a[i,j] 最原始的方程就是三角形那个，但是在此基础上还需要一些改进。。 1.DP有环怎么办? 别急,先别想着放弃DP,有时候环是可以避免的.这里在每一行中为避免相邻两格左右移动产生的环,可以先推向左的,再推向右的,而同向移动产生的那个“大”环就麻烦一点.其实有个很简单的窍门:先记录从下一行转移来的最优值,然后在本行中寻找代价最小的点,以这个点为起点分别向左向右推,因为最小的点显然是不需要从两侧的点过来的.这样就没有后效性了.. 2.递推的顺序: 递推有两种顺序,可以根据当前状态值推出所有可能的后继状态,也可以根据所有当前状态可能的前驱来推当前值,很多时候,当问题的状态比较有规律时,这两种方法是不相上下的.但是其他情况下一不小心就可能搞错.比如这题题目告诉我们的是从一个状态可行的所有走法(共四种),所以根据这个顺序去编是最保险的。因为这里一个状态的前驱不一定只是四个,边缘的点是特例,可能会有5个来源,所以DP的时候不要随便换状态转移顺序. 【代码】 

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a,b)(a<b?a:b)
int a[1002][1002];
int b[1002][1002];
int main()
{
    int n, i, j;
 
   scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    }
    for (i = 1; i <= n; i++)
    {
        a[i][0] = a[i][i];
        a[i][i + 1] = a[i][1];
    }
    memset(b, 0, sizeof(int) * 1002 * 1002);
    for (i = 1; i <= n; i++)   //最下面一层
        b[n][i] = b[n][i - 1] + a[n][i];
    b[n][n] = a[n][1] + a[n][n];
    for (i = n - 1; i >= 2; i--)	//求最下面一层每个位置的最小
        if (b[n][i] > b[n][i + 1] + a[n][i])
           b[n][i] = b[n][i + 1] + a[n][i];
    for (i = n - 1; i >= 1; i--)  //DP上面的每一层，此为DP的阶段
    {
        for (j = 1; j <= i; j++)  //状态转移
        {
            if (j == 1)  //对于每一个点，要考虑下
               b[i][j] = min(b[i + 1][i + 1], min(b[i + 1][j], b[i + 1][j + 1])) + a[i][j];
            else if (j != 1 && j != i)
               b[i][j] = min(b[i][j - 1],min(b[i + 1][j], b[i + 1][j + 1])) + a[i][j];
            else if (j == i)
               b[i][j] = min(b[i][j - 1], min(b[i + 1][1], min(b[i + 1][j], b[i + 1][j + 1]))) + a[i][j];
        }
        for (j = 1; j <= i; j++) //本层的DP 从前往后
        {
            if (j == 1) //特殊处理
               b[i][j] = min(b[i][j], b[i][i] + a[i][j]);
            else
            b[i][j] = min(b[i][j], b[i][j - 1] + a[i][j]);
        }
        for (j = i; j >= 1; j--)//本层的DP 从后往前
        {
            if (j == i) //特殊处理
               b[i][j] = min(b[i][j], b[i][1] + a[i][j]);
            else
                b[i][j] = min(b[i][j], b[i][j + 1] + a[i][j]);
        }
    }
    printf("%d\n", b[1][1]);
    return 0;
}