#include<iostream> (5488)#include<algorithm> #include<vector> using namespace std; int main() { int n; cin>>n; int k; cin>>k; vector<int> pos(n); for(int i=0;i<n;i++){ cin>>pos[i]; } //先对pos排序 sort(pos.begin(),pos.end()); int l=0,r=0; vector<int> cover(n); //双指针法，求出cover[0..n-1] //cover[i]表示在pos中下标i之后(包括i)共有多少个馅饼与pos[i]的距离在k之内 //比如pos: 1 1 2 3 4 5 5 //如果k=1,则对应的cover: 3 2 2 2 3 2 1 while(l<n){ while(r<n&;;&;;pos[r]-pos[l]<=k){ ++r; } cover[l]=(r-l); ++l; } /* dp[i][j]表示: 必须恰好有j次选择了吃馅饼， 从pos中下标i开始选择吃或者不吃馅饼, 一直选到pos中的最后一个位置所能吃到的最多馅饼数量 */ vector<vector<int>> dp(n); for(int i=0;i<n;i++) { dp[i].resize(3); } //必须选择吃2次馅饼，但此时只有最后一个馅饼,不符合题意，赋予-1方便后续比较 dp[n-1][2]=-1; //必须选择吃1次馅饼,但此时只有最后一个馅饼,必须也只能选择吃它 dp[n-1][1]=1; for(int i=n-2;i>=0;i--) { for(int j=1;j<3;j++){ /*如果i+cover[i]==n并且必须恰好要有2次选择吃馅饼, 说明此时这个馅饼一定不能选择吃 否则的话，假如我们选择吃它，就会剩下一次必须选择吃馅饼的机会 但却没有馅饼可吃了,所以直接dp[i][j]=dp[i+1][j]*/ if(i+cover[i]==n&;;&;;j==2){ dp[i][j]=dp[i+1][j]; } /*如果i+cover[i]==n并且必须恰好要有1次选择吃馅饼, 说明pos[i]这个馅饼一定要选择吃，因为这样会吃完pos[i]以及之后 的所有馅饼，一定是最多数量，直接dp[i][j]=cover[i]即可 */ else if(i+cover[i]==n&;;&;;j==1){ dp[i][j]=cover[i]; } /*如果i+cover[i]<n并且必须恰好要有1次选择吃馅饼(说明之前已经选择了一次,所以还剩下1次), 说明此时这个馅饼(pos[i])可以选择吃，也可以选择不吃，看哪个能吃到的数量更多就选择哪个方案 */ else if(i+cover[i]<n&;;&;;j==1){ dp[i][j]=max(cover[i],dp[i+1][j]); } /*如果i+cover[i]<n并且必须恰好要有2次选择吃馅饼(说明之前还没有一次选择吃馅饼,所以还剩下2次), 说明此时这个馅饼(pos[i])可以选择吃，也可以选择不吃，看哪个能吃到的数量更多就选择哪个方案 */ else if(i+cover[i]<n&;;&;;j==2){ dp[i][j]=max(dp[i+cover[i]][j-1]+cover[i],dp[i+1][j]); } } } // 从pos[0]开始决策，必须恰好只有2次选择吃馅饼的情况下所能吃到的最多数量即为答案 cout<<dp[0][2]<<endl; return 0; }