一些算法的复习（最短路径、最小生成树、dp）

暑假过去两个月，再一次对一些算法的复习：

最短路径：

Floyd- Warshall算法：

这个算法就是让我们去寻找从点i到点j的距离，有以下两种情况：

（1）. 两点直接到达的距离最短。

（2）. 两点之间通过1个或者1个以上节点连接到达的距离最短。

其中主要代码只有五行，通过不同的点去中转看看中转之后的点到达的距离与直接到达是否小，如果小就更新距离。

for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(e[i][j]>e[i][k]+e[k][j])
        e[i][j]=e[i][k]+e[k][j]  

Dijkstra算法:

这个算法就是找到一个顶点，然后看看这个顶点到其他点的最小距离。如果到下一个顶点的距离比当前顶点大，九成新更新距离。

具体步骤：

1、将所有顶点分为两部分：已知最短距离路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P只有一个顶点。我们这里用一个book记录那些点已经在集合P中。

2、设置源点s到自己的距离为0，若有源点能直接到达顶点，则距离为e[s][i],若不能到达此时距离为无穷大，这个我们定义99999999为无穷大。

3、在集合Q的所有顶点中选择离源点s最近的顶点u加入集合P中，并考察以u为起点的边，对每一条边进行松弛。

4、重复第3步，直到集合Q为空。

for(i=1;i<=n-1;i++)
  {
    min=inf;
    //找到离1号顶点最近的点 
    for(j=1;j<=n;j++)
    {
      if(book[j]==0&&dis[j]<min)
      {
        min=dis[j];
        u=j;
      }
    }
    book[u]=1;
    for(v=1;v<=n;v++)
    {
      if(e[u][v]<inf)
      {
        if(dis[v]>dis[u]+e[u][v])
          dis[v]=dis[u]+e[u][v];
      }
    }
  }

最小生成树：

kruskal算法：

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

这个算法实现就是先利用快排把从小到大排序，贪心算法取最优边，然后利用并查集判断两边是否已经在一个集合中。

核心代码：

  for(i=1;i<=m;i++)//开始从小到大枚举每一条边
  {
    if(merge(e[i].u,e[i].v))//利用并查集判断两个边是否已经在一个集合中
    {
      count++;
      sum=sum+e[i].w;
    }
    if(count==n-1)//到n-1条边后退出循环
      break;
  }

prim算法：

算法流程：

1、从任意一个顶点构造生成树，然后用book[]数组记录标记的点。

2、用dis[]数组记录生成树到各个顶点的距离

3、从dis[]数组中选出离生成树最近的顶点加入生成树中，如果dis[k]>e[j][k]，则重新更新dis[k]。

4、重复第三步，直到count==n.

核心代码：

  book[1]=1;//将1号顶点加入生成树
  count++;
  while(count<n)
  {
    min=inf;
    for(i=1;i<=n;i++)
    {
      if(book[i]==0&&dis[i]<min)
      {
        min=dis[i];
        j=i;
      }
    }
    book[j]=1;
    count++;
    sum+=dis[j];
    for(k=1;k<=n;k++)//扫描当前j所在的顶点，再以j为中间点，更新生成树到每一个非树顶点的位置 
    {
      if(book[k]==0&&dis[k]>e[j][k])
        dis[k]=e[j][k];
    }
  }

dp:

对于用动态规划的问题，其大大的减少了计算量，丰富了计算，它包括：背包问题（详解参照https://blog.csdn.net/qq_44859533/article/details/98972091）、动态三角形、还有最长、最大连续子序列。

最长连续子序列例题：

A numeric sequence of ai is ordered if a1 < a2 < … < aN.Let the subsequence of the given numeric sequence ( a1, a2, …, aN) be any sequence ( ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

解题思路：给定一个序列找出连续的递增子序列；

程序代码：

#include<stdio.h>
int main()
{
  int i,j,k,n,t;
  int a[2000];
  int len[2000];
  int max;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
  len[1]=1;
  for(i=2;i<=n;i++)
  {
    t=0;
    for(k=1;k<i;k++)
    {
      if(a[k]<a[i]&&t<len[k])
        t=len[k];
    }
    len[i]=t+1;
  }
  max=-1;
  for(i=1;i<=n;i++)
  {
    if(max<len[i])
      max=len[i];
  }
  printf("%d\n",max);
  return 0;
}