VOLIS - Dãy con không giảm dài nhất
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1011
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,d,f[maxn][maxn],a;
int main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%d %d",&n,&d);
for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) f[i][j] = oo;
for(int i = 0; i <= n; i++) f[i][0] = -oo;
for(int i = 1; i <= n; i++){
scanf("%d",&a);
for(int j = 1; j <= i; j++){
f[i][j] = f[i-1][j];
if(a + d >= f[i-1][j-1]) f[i][j] = min(f[i][j], max(f[i-1][j-1],a - d));
}
}
for(int i = n; i >= 1; i--) if(f[n][i] < oo){
printf("%d\n",i);
return 0;
}
}