感觉全世界就我赛时没有想到这道题是滑动窗口
言归正传，这道题有两个限制条件：1.窗口大小不超过k；2.相邻元素之差为1。
对于第一点通过限制双端队列的size就行，对于第二点，我是先把数组排序，之后进行统计出现次数，并用结构体存储，然后滑动窗口解决问题，如果 新插入元素 - 1 != 前一个元素，那么就清空队列，然后插入新的元素。
接下来放代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;struct st{ll num1, num2;
};
void slove()
{ll n, k, tool = 1;cin >> n >> k;ll a[n + 10];st b[n + 10];for(ll i = 1; i <= n; i ++){cin >> a[i];}sort(a + 1, a + 1 + n);ll num = 1;for(ll i = 1; i < n; i ++){if(a[i] == a[i + 1])tool ++;else{b[num].num2 = a[i];b[num ++].num1 = tool;tool = 1;}}b[num].num1 = tool;b[num].num2 = a[n];deque <st> q;q.push_back(b[1]);ll ans = b[1].num1;tool = b[1].num1;for(ll i = 2; i <= num; i ++){if(b[i].num2 - 1 == q.back().num2){q.push_back(b[i]);tool += b[i].num1;if(q.size() > k){tool -= q.front().num1;q.pop_front();}ans = max(ans, tool);}else{ans = max(ans, tool);tool = b[i].num1;ans = max(ans, tool);while(!q.empty()){q.pop_back();}q.push_back(b[i]);}}cout << ans << endl;return ;
}
int main()
{ll t = 1;cin >> t;while(t --){slove();}return 0;
}
这道题我赛事的思路是dp，滑动窗口是赛后听群友说才恍然大悟，明明知道dp会T，但因为不想写自己想的前缀和模拟，就硬着头皮写dp了，属实有些不理智了。。。（主要是最近一直在练dp，看到这道题有点像，就很想检验成果，结果。。。）
把dp的代码也放一下把，就当作是记录了
#include<bits/stdc++.h>
#define ll long long
using namespace std;struct st{ll num1, num2;
};
void slove()
{ll n, k;cin >> n >> k;ll a[n + 10];st b[n + 10];for(ll i = 1; i <= n; i ++){cin >> a[i];}sort(a + 1, a + 1 + n);ll tool = 1;ll num = 1;for(ll i = 1; i < n; i ++){if(a[i] == a[i + 1])tool ++;else{b[num].num2 = a[i];b[num ++].num1 = tool;tool = 1;}}b[num].num1 = tool;b[num].num2 = a[n];ll dp[num + 10];memset(dp, 0, sizeof(dp));ll ans = 0;for(ll i = 1; i <= num; i ++){dp[i] = b[i].num1;ans = max(ans, dp[i]);}for(ll i = 2; i <= k; i ++){for(ll l = num; l >= i; l --){if(b[l].num2 - 1 == b[l - 1].num2 && dp[l - 1] != 0)dp[l] = max(dp[l - 1] + b[l].num1, dp[l]);ans = max(ans, dp[l]);}}cout << ans << endl;return ;
}
int main()
{ll t = 1;cin >> t;while(t --){slove();}return 0;
}
这周打算继续刷dp，去看看区间dp，加油吧。
