【无评级杂题】DP/贪心

题目

这题后来看了看网上的思路，发现贪心就能做，亏我还写了个O(2*N)的DP...浪费时间了属于是

my-code

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;
int n,k,a[100000+5],dp[100000+5][2];
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	//dp i j represents that the max_ans of the game just include the formal i ones and j=1 represents that the last one is chosen while j=0 is not be chosen. 
	//dp[i][0]=(dp[i-1][1],dp[i-1][0]);
	//dp[i][1]=1+max(dp[j][1],dp[j][0]) ;j is the max num which is <=ai-k
	dp[1][1]=1;dp[1][0]=0;
	for(int i=2;i<=n;i++)
	{
		dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
		int j,flag=0;
		for(j=i-1;j>=1;j--)
		{
			if(a[i]-a[j]>=k)
			{
				flag=1;
				break;
			}
		}
		if(flag==1)
			dp[i][1]=1+max(dp[j][1],dp[j][0]) ;
		if(flag==0)
			dp[i][1]=1;
	}
	cout<<max(dp[n][1],dp[n][0]);
	
	return 0;
}