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

本文主要是介绍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（论数据的重要性）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---