华师一附中OI组

标题: 最长不下降序列LICS [打印本页]
作者: diggersun    时间: 2015-10-31 20:42
标题: 最长不下降序列LICS
题目：给定一个序列，求它的一个子序列，保证后面一个数字不小于前面的数字，并且最长。
比如 1 3 5 9 7 8 6 4 2 0 这个序列，1 3 5 7 8 是它的一个子序列，长度为5，后面的数字不小于前面的数字，并且，找不到比它更长的。
作者: diggersun    时间: 2015-10-31 20:46
我上课时候讲的是标准做法，虽然略有一点繁琐，但是清晰，扩展性强，同学们要认真去理解。虽然有的书上或者网上讲的比我的简单，但是，损失了一点扩展性，等熟练之后大家也可以学习网上的做法。
思路：用a数组表示每个数字的值，l数字表示目前最大的长度，f数组表示这个数字的前驱，p数组表示路径。
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. int a[11]= {0,1,7,3,5,9,2,8,6,4,99}; //假设有9个数字分别是1,7,3,5,9,2,8,6,4，第一个位子空着，最后一个是假标记
  5. int l[11]; //到当前为止的最长不下降序列的长度
  6. int f[11]; //当前最优决策时的前驱的编号
  7. int p[11];//输出路径时用的数组
  8. int i,j;
  9. int main()
  10. {
  11.     for (i=0; i<=10; i++)
  12.     {
  13.         l[i]=1;  //至少的长度是1
  14.         f[i]=-1; //不需要前驱
  15.     }

  17.     for(i=2; i<=10; i++) ///枚举当前位置
  18.         for (j=1; j<i; j++) ///枚举当前位置前面的所有可能
  19.             if (a[j]<=a[i])  ///不下降
  20.                 if (l[j]+1>=l[i])        ///最长
  21.                 {
  22.                     l[i]=l[j]+1;  ///决策
  23.                     f[i]=j;       ///记录前驱
  24.                 }

  26.     for (i=0; i<=10; i++)
  27.         cout<<setw(4)<<a[i];
  28.     cout<<endl;
  29.     for (i=0; i<=10; i++)
  30.         cout<<setw(4)<<l[i];
  31.     cout<<endl;
  32.     for (i=0; i<=10; i++)
  33.         cout<<setw(4)<<f[i];
  34.     cout<<endl;
  35.     i=0;
  36.     p[i]=10; ///最后一个绝对是最长的
  37.     while (f[p[i]]!=-1)  ///还有前驱
  38.     {
  39.         i++;
  40.         p[i]=f[p[i-1]];
  41.     }

  43.     for (j=i; j!=-1; j--) cout<<a[p[j]]<<' '; ///输出最后的路径
  44.     return 0;
  45. }

复制代码


作者: diggersun    时间: 2015-10-31 20:46
上面的做法很直观但是浪费也是很严重的，怎么改进呢
作者: diggersun    时间: 2015-10-31 20:46
diworth定理
作者: SilverMOR    时间: 2016-2-17 14:34
那么然后呢
作者: 张笑宇    时间: 2018-7-27 21:28
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,a[10010],d[10010],len;
  5. int main()
  6. {
  7.     cin>>n;
  8.     for (int i=1; i<=n; i++) cin>>a[i];
  9.     len=1,d[1]=a[1];
  10.     for (int i=2; i<=n; i++)
  11.     {
  12.         if (a[i]>=d[len])///不下降
  13.             d[++len]=a[i];
  14.         else
  15.         {
  16.             int l=0,r=len,mid;
  17.             while (l<r)
  18.             {
  19.                 mid=(r-l)/2+l;
  20.                 if (d[mid]>a[i]) r=mid;
  21.                 else l=mid+1;
  22.             }
  23.             d[l]=a[i];
  24.         }
  25.     }
  26.     cout<<len;
  27.     return 0;
  28. }
复制代码
作者: 黄煦喆    时间: 2018-7-28 11:44
  1. #include<iostream>
  2. using namespace std;
  3. int a[101],l[101],f[101],n;
  4. void dfs(int x)
  5. {
  6.     if(f[x]!=-1)dfs(f[x]);
  7.     cout<<a[x]<<' ';
  8. }
  9. int main()
  10. {
  11.     cin>>n;
  12.     for(int i=1;i<=n;++i)cin>>a[i],l[i]=1,f[i]=-1;
  13.     for(int i=1;i<n;i++)
  14.         for(int j=i+1;j<=n;j++)
  15.         if(a[j]>=a[i]&&l[j]<l[i]+1)
  16.         {
  17.             l[j]=l[i]+1;
  18.             f[j]=i;
  19.         }
  20.     int k=1,t=1,maxa=-1;
  21.     while(t<=n)
  22.     {
  23.         if(l[t]>maxa)maxa=l[t],k=t;
  24.         t++;
  25.     }
  26.     dfs(k);
  27.     return 0;
  28. }
复制代码
作者: zhwang    时间: 2018-7-29 21:47
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. int n;
  5. int a[10001];
  6. int f[10001];
  7. int main()
  8. {
  9.         scanf("%d",&n);
  10.         for(int i=1;i<=n;i++)
  11.         {
  12.                 scanf("%d",&a[i]);
  13.         }
  14.         f[1]=1;
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.                 for(int j=i-1;j>=1;j--)
  18.                 {
  19.                         if(a[j]<=a[i])
  20.                         {
  21.                                 f[i]=f[j]+1;
  22.                                 break;
  23.                         }
  24.                 }
  25.         }
  26.         int ans=0;
  27.         for(int i=1;i<=n;i++)
  28.         {
  29.                 ans=max(ans,f[i]);
  30.         }
  31.         printf("%d",ans);
  32.         return 0;
  33. }
复制代码
作者: 黄煦喆    时间: 2018-8-2 22:21
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,len,l,r,mid;
  5. int a[101],b[101];
  6. int main()
  7. {
  8.     cin>>n;
  9.     for(int i=1;i<=n;i++)cin>>a[i];
  10.     b[1]=a[1];
  11.     len=1;
  12.     for(int i=2;i<=n;i++)
  13.         if(a[i]>=b[len])b[++len]=a[i];
  14.         else
  15.         {
  16.             int k=upper_bound(b+1,b+len+1,a[i])-b;
  17.             b[k]=a[i];
  18.         }
  19.     cout<<len<<endl;
  20.     return 0;
  21. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2