题意:给你一个数组。
题目定义一个关系。两个数 a . b a.b a.b,当且仅当 a b 2 |a-b|\leq2 ab2时, a , b a,b a,b在一个分组中,让你求出一个最大的分组,输出元素个数。
可以对任一位置的数进行加一或者减一 一次。
思路:考虑 d p dp dp,先对数组进行排序,然后, d p dp dp数组为 d p [ i ] [ j ] dp[i][j] dp[i][j],意为:以 i i i为最后一个数的时候经过 j j j次变化得到的最大的答案。这个变化次数不是说一共的变化次数,而是说: i i i由上一个数 k k k转移过来, i , k 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;
}