New Year Parties

题意给定你n个点，每个点可以停在原地或者向左向右，问最多能有多少个不重合的点 还有 最少能有多少个点。
解题报告：看题目就感觉是dp题 但听大佬说不能dp做？
但我抱着侥幸的心里写了写dp，一开始确实wa了，后来看了看状态转移 ，我们dp数组定义的是考虑前i个人并且第i个人的状态是向左、向右、不动 ，如果每个状态都能被三个状态转移的话 ，其实是有问题的，我们没有保证i-1个的坐标是比i要小于等于的，如果上一个人的坐标比i大 那么就会有问题 例如dp[i][2]还是会被dp[i][1]所更新到，所以我想把状态定义为以i为结尾，且i为最大的状态，保证前一个点<=后一个点就行了。
ac代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010;
int x[N];
bool st[N];
int dp[N][3];	//考虑前i个人 第i个人往左不动往右 的最大房间数
int main()
{
   	
	int n;
	cin>>n;
	int minv=1e9;
	for(int i=1;i<=n;i++)
	{
   
		cin >> x[i];
		st[x[i]]=true;
		minv=min(minv,x[i]);
	}
	sort(x+1,x+1+n);
	int lf=minv;
	int res_min=1e9;
	// for(int i=1;i<=n;i++)
	// {
   
	// 	if(st[i] &&	i>lf+2)
	// 	{
   
	// 		res_min++;
	// 		lf=i;
	// 	}
	// }
	memset(dp,0x3f,sizeof dp);
	dp[1][0]=1;
	dp[1][1]=1;
	dp[1][2]=1;
	for(int i=2;i<=n;i++)
	{
   
		if((x[i-1]+1)<=x[i]) dp[i][0]=min(dp[i][0],dp[i-1][1]+((x[i-1]+1)<x[i]));
		dp[i][0]=min(dp[i][0],dp[i-1][0]+(x[i-1]<x[i]));
		dp[i][0]=min(dp[i][0],dp[i-1][2]+1);
		dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
		dp[i][1]=min(dp[i][1],dp[i-1][1]+(x[i-1]<x[i]));
		dp[i][1]=min(dp[i][1],dp[i-1][2]+1);
		dp[i][2]=min(dp[i][2],dp[i-1][2]+(x[i-1]<x[i]));
		if(x[i-1]+1<=x[i]-1)
		dp[i][2]=min(dp[i][2],dp[i-1][1]+(x[i-1]<x[i]-2));
		if(x[i-1]<=x[i]-1)
		dp[i][2]=min(dp[i][2],dp[i-1][0]+(x[i-1]<(x[i]-1)));
	}
	res_min=min(dp[n][2],min(dp[n][0],dp[n][1]));
	memset(dp,0,sizeof dp);
	dp[1][0]=1;
	dp[1][1]=1;
	dp[1][2]=1;
	
	for(int i=2;i<=n;i++)
	{
   
		if((x[i-1]+1)<=x[i]) dp[i][0]=max(dp[i][0],dp[i-1][1]+((x[i-1]+1)<x[i]));
		dp[i][0]=max(dp[i][0],dp[i-1][0]+(x[i-1]<x[i]));
		dp[i][0]=max(dp[i][0],dp[i-1][2]+1);
		dp[i][1]=max(dp[i][1],dp[i-1][0]+1);
		dp[i][1]=max(dp[i][1],dp[i-1][1]+(x[i-1]<x[i]));
		dp[i][1]=max(dp[i][1],dp[i-1][2]+1);
		dp[i][2]=max(dp[i][2],dp[i-1][2]+(x[i-1]<x[i]));
		if(x[i-1]+1<=x[i]-1)
		dp[i][2]=max(dp[i][2],dp[i-1][1]+(x[i-1]<x[i]-2));
		if(x[i-1]<=x[i]-1)
		dp[i][2]=max(dp[i][2],dp[i-1][0]+(x[i-1]<(x[i]-1)));
	}
	int res=max(dp[n][0],max(dp[n][1],dp[n][2]));
	cout<<res_min<<' '<<res<<endl;
	return 0;

}