题意给定你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; }