Codeforces 474E Pillars（论数据的重要性）

  今天做到这道题，一看是一道很水的最长不下降序列吧，但是数据超级大，怎么办，突发奇想，因为每一次都要和前面比，那么需要从第一个状态推现在的状态，那么有数据比较水，也许前面的600个状态就可一推理到，那么直接从他的钱600个状态推就水过了

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

typedef long long int ll;

const int N=100100;

int n,K;
ll h[N],sum[N],path[N],ans[N];

int main()
{
	cin>>n>>K;
	sum[1]=1; 
	int maxl=1;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		sum[i]=1;
		for(int j=max(1,i-600);j<i;j++)
		{
			if(abs(h[j]-h[i])>=K&&sum[j]+1>sum[i])
			{
				sum[i]=sum[j]+1;
				path[i]=j;//下一个是j
			}
			if(sum[i]>sum[maxl])
			{
				maxl=i;
			}
		}
	}
	cout<<sum[maxl]<<endl;
	int T=path[maxl];
	int cnt=0;
	ans[cnt]=maxl;
	while(T)
	{
		ans[++cnt]=T;
		T=path[T];
	}
	for(int i=cnt;i>=0;i--){
		cout<<ans[i]<<" ";
	}
	return 0;
}

Codeforces 474E Pillars（论数据的重要性）

原文：http://blog.csdn.net/u013076044/article/details/42319839