腾讯马拉松之小明系列问题——小明序列

                                                                  小明系列问题——小明序列

题目链接:Click Here~

题目分析：

    一看完题目，就猜到了是LIS。但是，到最后也没写出来。看了别人的解题思路才知道。弱爆了，又可惜了一道好题啊 T_T

    既然是看别人的，那我也不想多解释了。直接给出博客Click。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int n,d,a[N],alen[N];
int LIS()
{
    int ret = 0;
    vector<int> vet;
    vector<int>::iterator it;
    for(int i = 1;i <= n;++i){
       it = lower_bound(vet.begin(),vet.end(),a[i]);
//       if(it == vet.end())
//         alen[i] = vet.size()+1;
//       else
         alen[i] = it - vet.begin()+1;
       if(i-d >= 1){
          if(vet.size() == alen[i-d]-1)    //已经是最后一个
            vet.push_back(a[i-d]);
          else
          if(vet[alen[i-d]-1] > a[i-d])   //跟以前序列的最后一个比，取小的
            vet[alen[i-d]-1] = a[i-d];
       }
       ret = max(ret,alen[i]);
    }
    return ret;
}
int main()
{
    while(~scanf("%d%d",&n,&d))
    {
        for(int i = 1;i <= n; ++i){
           scanf("%d",&a[i]);
        }
        printf("%d\n",LIS());
    }
    return 0;
}

腾讯马拉松之小明系列问题——小明序列

原文：http://blog.csdn.net/zhongshijunacm/article/details/19843367