题意:给你一个数组。
题目定义一个关系。两个数 a.b,当且仅当 ∣a−b∣≤2时, a,b在一个分组中,让你求出一个最大的分组,输出元素个数。
可以对任一位置的数进行加一或者减一 一次。
思路:考虑 dp,先对数组进行排序,然后, dp数组为 dp[i][j],意为:以 i为最后一个数的时候经过 j次变化得到的最大的答案。这个变化次数不是说一共的变化次数,而是说: i由上一个数 k转移过来, i,k一共的变化次数,显然最多一共能变化2次。那么转移方程就可以写了。
遍历数组的每一个数,显然这个数可以变成三个数(+1,0,-1)其中(+1,-1)都是变化一次的,0是不变的。然后转移就完事辽。
细节见代码。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int t,n,a[N];
int f[333][3],now;
int main(){
for(scanf("%d",&t);t;t--){
scanf("%d",&n);
int ans=1;
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
int x=a[i];
for(int j=2;j>=1;j--)f[x+1][j]=max({f[x+1][j-1],f[x][j-1],f[x-1][j-1]})+1;
for(int j=2;j>=0;j--)f[x][j]=max({f[x][j],f[x-1][j],x>=2?f[x-2][j]:0})+1;
for(int j=2;j>=1;j--)f[x-1][j]=max({f[x-1][j-1],x>=2?f[x-2][j-1]:0,x>=3?f[x-3][j-1]:0})+1;
}
for(int i=0;i<244;i++)for(int j=0;j<3;j++)ans=max(ans,f[i][j]);
printf("Case %d: %d\n",++now,ans );
}
return 0;
}