[图论]一个叫做LIS(最长不下降子序列)的东西

啊哈磊

输入数据：
10
2 8 10 1 5 1 7 8 6 5
输出数据：
4

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {
   
5.   int a[1000],g[1000];
   
6.   int i,k,n,max;
   
7.    
   
8.   scanf("%d",&n);
   
9.   for(i=1;i<=n;i++) scanf("%d",&a[i]);
   
10.   //动规边界，初始化
    
11.   g[1]=1;
    
12.   //动规开始
    
13.   for(i=2;i<=n;i++)
    
14.   {
    
15.     g[i]=1;//初值，这里很用重要。。。。。位置不要写错，要在for(j)循环的外面
    
16.     //每次找i前面所有的数，所以是1到i-1
    
17.     for(k=1;k<=i-1;k++)
    
18.     {
    
19.       //枚举前面的每个数是不是比当前这个数小, 注意这里是不下降子序列，所以是小于等于
    
20.       if( a[i] <= a[k])
    
21.       {
    
22.         if( g[i] < g[k]+1 )
    
23.           g[i] = g[k] + 1;
    
24.       }        
    
25.     }
    
26.   }
    
27.   //g 数组里面找最大的1个
    
28.   max=0;
    
29.   for(i=1;i<=n;i++)
    
30.   {
    
31.     if( max < g[i] )
    
32.       max = g[i];
    
33.   }
    
34.   printf("%d",max);
    
35.   return 0;
    
36. }

复制代码

4k-Rn

xuexile
.................