本文主要是介绍hdu5421 小明系列问题——小明序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有多组测试数据，每组数据的n和d表示，有n个数，求相邻元素间距大于d的最长上升序列。(1<=n<=10^5 , 0<=d<=10^5)
正常的LIS输入第i个数时在处理完0到i-1的队列中找到一个合适位置把a[i]插入。本题有个限制条件d,所以每次只能在处理完0到i-d的队列中找到一个合适位置把a[i]插入,这样我们延缓更新队列即可，在处理第i个数据时，队列只需更新到a[i-d]的位置即可。
/* ***********************************************
Author :fisty
Created Time :2014/12/30 16:32:28
File Name :hdu4521.cpp
************************************************ */#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define MAX_N 101000
#define INF 0x3f3f3f3f
int n, d; //个数与间距
int dp[MAX_N];
int arr[MAX_N], aux[MAX_N];
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin.tie(0);std::ios::sync_with_stdio(false);while(scanf("%d%d", &n, &d) != EOF){memset(aux,0x3f,sizeof(aux));int max = 0;for(int i = 1;i <= n;i++){scanf("%d",& arr[i]);int j = lower_bound(aux + 1, aux + 1 + n, arr[i]) - aux;dp[i] = j;//间距大于dif(i > d) aux[dp[i-d]] = min(aux[dp[i-d]],arr[i-d]);/*间距为0aux[j] = arr[i];*/if(dp[i] > max) max = dp[i];}for(int i = 1;i <= n; i++){printf("%d", dp[i]);}printf("\n\n");printf("%d\n",max);}return 0;
}
这篇关于hdu5421 小明系列问题——小明序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
