1道动态规划(搬箱子)、KMP算法、图(Prim算法、1道哈夫曼树

1.最长递增子序列

华华要给厂里进一批新箱子共n个(n<=500)，编号为1到n，用一个正整数ai(1<=ai<=10000)(1<=i<=n)来表示编号为i的箱子的高度。现在华华要按照编号从小到大的顺序选出m个箱子运到厂房，要确保编号大的箱子比编号小的箱子高。也就是对于任意的i<j有ai<aj，那么m最大可以是多少呢？
思路：其实就是求最大递增子序列。
设箱子高度数组为a。
例如a[i] = [1 7 3 5 9 4 ] m = 4。
考虑子问题：
以数组下标i结尾的子序列长度L(i)。
考虑所有的j满足j<i,a[j]<a[i]。
L[i] = max(L[j] 1,1)。
过程：
初始化一个下三角二维数组record[i][j]，用于记录从下标为j的数开始到下标为i的数中的最大递增子序列长度。显然当i == j时，record[i][j] = 1。
再用一个数组maxnum[num]记录以下标为j结尾的最长子序列的长度。
则有：
maxnum[p] = max{record[p][0],record[p][1],…record[p][p]}。
求出maxnum数组中的所有元素后，最长递增子序列的长度就是maxnum中的最大值。

#include<iostream>

using namespace std;

int main(){
    int num;
    cin>>num;   //输入箱子数量
    int* height = (int*)malloc(sizeof(int)*num);  //记录箱子高度
    int boxheight;   //用于输入箱子高度
    for(int i=0;i<num;i  ){
        cin>>boxheight;
        height[i] = boxheight;
    }

    int* maxnum = (int*)malloc(sizeof(int)*num);   //上面说的maxnum数组

    int** record = (int**)malloc(sizeof(int*)*num);   //上面说的record数组
    for(int i=0;i<num;i  ){
        record[i] = (int*)malloc(sizeof(int) * (i 1));
        maxnum[i] = 0;
    }
    int cmpHeight;
    for(int i=0;i<num;i  ){
        cmpHeight = -1;   //用于更新maxnum
        for(int j=0;j<=i;j  ){
            if(j == i){
                record[i][j] = 1;
            }else{
                if(height[i] <= height[j]){
                    record[i][j] = 1;
                }else{
                    record[i][j] = maxnum[j]   1;
                }
            }
            if(cmpHeight<record[i][j]){
                cmpHeight = record[i][j];
            }
        }
        maxnum[i] = cmpHeight;
    }
    

    int realmax = 0;     //本题结果
    for(int i=0;i<num;i  ){
        if(realmax<maxnum[i]){
            realmax = maxnum[i];   //求maxnum数组最大值
        }
    }
    cout<<realmax;   //本题结果
    return 0;
}

2.KMP算法

KMP算法主要用于模式匹配，优点主要在于：比如从aaaaaaaab串中找到aaab这个子串。每次都比较四次发现b和a匹配不上才向后移动aaab这个字串，时间复杂度太高。
KMP算法可以解决这一点。
具体过程如下：
1.先求子串的prefix表。
何谓prefix表？所谓prefix表就是一个串最长相等前后缀的长度。例如：abcba。其长度为4的前缀为abcb，长度为4的后缀为bcba，两者不相等。再看长度为3的前缀abc，长度为3的后缀为cba，不相等。长度为2的前缀ab，长度为2的后缀ba，两者不相等。长度为1的前缀a，长度为1的后缀a，两者相等。所以abcba这个串的prefix值就是1.
对于给定的子串，求其所有的前缀（自己不算，长度为1的前缀不算），再对所有前缀求prefix值，就构成了prefix表。
例如：
对于另一个串ababcabaa
其所有前缀和对应的prefix值如下：
表一

能得到一个规律：
看第2，3行，aba的prefix值是1，abab的prefix值为2。找的时候设置一个头指针，一个尾指针。当求aba的prefix值的时候，头指针len指向index = 0的a.尾指针tailPoint指向index = 2的a,进而求abab的子串。len向后移动一格，tailPoint也向后移动一格，两者若能正好匹配，abab的prefix的值也就是在aba的基础上 1。
同理可以看5，6，7行。ababca的prefix值是1,len和tailPoint同时后移一格，两个b又相互配上，则ababcab的prefix值为1 1 = 2，再同时后移一格，两个a又相互配上，ababcaba的prefix值为2 1 = 3.
话说这是后移一格配上的情况，那么没配上的怎么算呢？
注意这里绝对不是没配上就简单地填上0。例如现在的prefix值为3,他没配上，之能证明下一个prefix不可能是4.有没有可能是1，2呢？有可能。
如下图，当求ababcabaa这个串的prefix值的时候，len指向的b不等于tailPoint指向的a。

这个时候prefix这个位置不能填0。具体应该怎么做？根据KMP算法，Knuth找到prefix[len]的的值，也就是现在b下面正对着的那个值，为2。将len更新为prefix[len]。此时len指向p[1]的b。由前后缀相等可知，最后一个位置的prefix值填不上4，就等于填不上2。于是他就决定把len更新为prefix[len-1]。也就是红箭头所指向的这个b左下角的那个1。做的更新操作是：len = prefix[len-1]。也就是试试前缀为a能不能跟最后的这个字符匹配上。这是一个递归的操作，每次回溯的对象是各前缀，看看这个前缀能不能跟后缀匹配上。如果匹配上了，就将现在的len 1赋值给当前的prefix。当然还有一种特殊情况，如果回溯到len = 0，且还是匹配不上，那就没必要再回溯了，再回溯就成了死循环，这个时候就认命吧，再要求prefix的这个位置填上0，因为真的没有前缀能和他匹配了。

void prefixTable(char* c1,int* (&table),int tableSize){
	/*
		table --> prefix表
		tablesize -->  prefix表的长度
		c1  -->  要求prefix表的字符串。
	*/
    table[0] = 0;

    int len = 0;    //既是前index又是截止到更新前的最大相同前后缀
    int tailPoint = 1;   //尾指针
    while(tailPoint<tableSize){
        if(charEquals(c1[len],c1[tailPoint])){
            len  ;                        //匹配上了这句话等于完成了两步操作，1)将当前的最大相同前后缀长度 1。  2)头指针后移一格。
            table[tailPoint  ] = len;     //赋值给当前要求的prefix的值后尾指针 1.
        }else{
            if(len == 0){
                table[tailPoint  ] = 0;  //上面所说的特殊情况
            }else{
                len = table[len-1];      //回溯递归
            }
        }
    }

    //加入-1,向后移动
    for(int i=tableSize-1;i>0;i--){
        table[i] = table[i-1];
    }
    table[0] = -1;
}

这就基本求出prefix表了，此时已经得到一个半成品prefix表，为[0 1 2 0 1 2 3 1]还差最后一步，将这个prefix表整体后移一个位置，并将首元素填成-1。就变成了[-1 0 0 1 2 0 1 2 3]。这就是我们求出的prefix表。
2.进行模式匹配
如图，要在串z “abababababcabaab”中寻找子串p “ababcabaa”。
第一步将p及上一步求出的prefix表与串z对齐。逐个匹配，a-a b-b a-a b-b a≠c,发现不等于，读取此时读头下标即c对准的这个2。下一步将p[2]对准当前位置。并从这个位置开始向后比较。b = b, a≠c。c下标为2,再将p[2]对准这个位置，继续向后比较。a = a, b = b，a≠c，再将p[2]对准当前位置，向后比较。终于，下一次，串成功匹配。
这里值得注意一种特殊情况，如果移动后的子串第一个字符仍无法匹配，则继续后移子串。

代码如下：

bool KMP(char* c1,char* c2,int* table){  //table即为前缀表prefix
    bool result = false;
    //在c2中查找c1。
    int c2Pointer = 0;   //c2串中的指针,初始为0.
    int c1Pointer = 0;   //c1串中的指针,初始为0.
    while(strlen(c2)-c2Pointer>=strlen(c1)-c1Pointer){   //如果子串中未匹配的字符个数大于父串中剩余的字符个数，就匹配失败。返回result,false。
        if(c2Pointer >= strlen(c2)){  //子串下标大于等于子串长度，模式匹配成功。
            result = true;
            break;
        }
        if(charEquals(c1[c1Pointer],c2[c2Pointer])){  //如果c1当前字符等于c2当前字符，两指针后移。
            c1Pointer  ;
            c2Pointer  ;
        }else{
            if(table[c1Pointer] != -1){
                c1Pointer = table[c1Pointer];  //父串中的指针不动，根据prefix表移动子串的指针。
            }else{
                c2Pointer  ;  //上述特殊情况。
            }
        }
    }
    return result;
}

至此，KMP算法结束。

3.Prim算法

克鲁斯卡尔和普利姆算法是在一个图中求最小生成树的算法。其中普利姆算法适用于结点数少于边的时候。
思路：将结点分为U集和V集。初始，所有结点都在U集里，V集为空。
从U集里任选一个结点到V集。
接下来重复下列操作至V集中包含全部结点，U集为空。
1.从U、V集里各选取一个结点A，B，使A,B间的距离大于任何U集和V集中的结点距离。
2.将B结点加入U集。
代码如下：

#include<bits/stdc  .h>
using namespace std;

bool allTraverse(bool* hasTraverse,int num){
	/*
		若hasTraverse数组全为true,返回true,否则返回false.
	*/
    for(int i=0;i<num;i  ){
        if(hasTraverse[i] == false){
            return false;
        }
    }
    return true;
}

void pushNode(bool* hasTraverse,int num,queue<int> &q){
	/*
		将hasTraverse数组中所有为false的元素全部入队列。
	*/
    for(int i=0;i<num;i  ){
        if(hasTraverse[i] == false){
            q.push(i);
        }
    }
}

int main() {
    int num;
    while(cin>>num){
        if(num == 0){
            break;
        }
        int graph[num][num];   //邻接矩阵
        bool hasTraverse[num];   //判断各结点是否在V集中。
        queue<int> q;            //用于记录在U集的结点。
        for(int i=0;i<num;i  ){           //初始化
            for(int j=0;j<num;j  ){
                graph[i][j] = INT_MAX;
            }
            hasTraverse[i] = false;
        }
        int node1,node2,dist;
        for(int i=0;i<num * (num-1) / 2;i  ){   //输入图的相关信息
            cin>>node1>>node2>>dist;
            graph[node1-1][node2-1] = dist;
            graph[node2-1][node1-1] = dist;
        }
        hasTraverse[0] = true;

        int minLength = 0;  //用于记录最小生成树的权值。
        int minDist;    //用于记录每回U集和V集中结点距离的最小值。
        int currentNode,newNode;  //newNode-->每回从U集中选取的要进入V集的结点。
        while(true){
            if(allTraverse(hasTraverse,num)){  //如果全在V集中，结束循环。
                break;
            }else{
                minDist = INT_MAX;
                pushNode(hasTraverse,num,q);  //将所有应处于U集的元素入队列。
                //下面将要找到U集中的元素和V集中的元素中的最小距离。
                while(!q.empty()){
                    currentNode = q.front();
                    q.pop();

                    for(int i=0;i<num;i  ){
                        if((hasTraverse[i] == true)&&(graph[i][currentNode] < minDist)){
                            newNode = currentNode;
                            minDist = graph[i][currentNode];
                        }
                    }
                }
                hasTraverse[newNode] = true;   //将选出来的元素入V集。
                minLength  = minDist;     //更新最小生成树权
            }
        }
        cout<<minLength<<endl;   //输出结果
    }
    return 0;
}

至于克鲁斯卡尔算法，再过几天可能会看一下。

4.哈夫曼树

在一棵树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果树中结点带有表示某种意义的权值，那么从根节点到达该结点的路径长度再乘以该结点的权值就被称为该结点的带权路径长度。树中所有叶子结点的带权路径长度之和为该树的带权路径长度和。给定n个带有权值的结点，以它们为叶子节点构造一棵带权路径长度之和最小的二叉树，即为哈夫曼树，注意哈夫曼树有可能不唯一，能求的只能是最小带权路径长度和。
给定n个数，以它们为叶子节点构造哈夫曼树，求最小带权路径长度和。
思路：利用优先队列，先将这几个数入优先队列，选出最小的两个数，作为叶子节点，将它们的和作为新的叶子节点入优先队列，直到优先队列中的数的个数为1.
在循环中累计最小带权路径长度和。
唯一需要注意的是，优先队列每次选出的是权值最大的两个数，而不是权值最小的两个数。在入队列的时候可以将该结点以相反数入队列，出队列的时候再取一个相反数即还原。

#include<bits/stdc  .h>
using namespace std;

/*
 * 哈夫曼树，
 * 思路：
 * 1.优先队列，各数入队列。
 * 2.最小的两个数出优先队列。
 * 3.利用result累计所有结点的值与权值的乘积之和。
 */
int main() {
    /*
     * num   叶节点个数
     * inputNum  用于输入叶节点的值
     * nodeNum1,nodeNum2 用于记录每次选中的两个叶节点
     */
    int num,inputNum,nodeNum1,nodeNum2,result;   //题目要求输出的所有结点的值与权值的乘积之和。
    priority_queue<int> q;                       //优先队列。
    while(cin>>num){
        result = 0;     //每次求解结果清零。
        for(int i=0;i<num;i  ){
            cin>>inputNum;
            q.push(-inputNum);   //叶节点的值的相反数入队列
        }
        while(q.size()>1){
            /*
             * 值最小的两个叶节点出队列。
             */
            nodeNum1 = -(q.top());
            q.pop();
            nodeNum2 = -(q.top());
            q.pop();


            result  = nodeNum1 nodeNum2;

            q.push(-nodeNum1-nodeNum2);   //新的叶节点入队列。
        }
        q.pop();    //将队列清空，方便下次计算。
        cout<<result<<endl;
    }
    return 0;
}

这篇好文章是转载于：学新通技术网