/* 先将a数组从小到大排序 dp[i][j][k]表示到以第i个数为结尾的，且第i个数改了j次，第i个数改动值为k-1的集合最大值 ans是dp过程中的最大集合大小 状态转移： 首先是到i改动为0次的情况： 如果a[i]-a[i-1]<=2,dp[i][0][1]=dp[i-1][0][1]+1 否则dp[i][0][1]=1 然后是j:1->2 k:0->2 先给定初始状态值 dp[i][j][k]=1 然后是枚举i-1的所有修改状态l:0->2 ai是a[i]修改后的值，aj是a[i-1]修改后的值 这里的状态转移分两种， 一种是第i个数不修改，dp[i][j][1]直接由dp[i-1][j][l]转移得到 二种是第i个数修改，dp[i][j][0|2]有dp[i-1][j-1][l]转移得到 dp过程中用不断更新ans 注意要使冗余状态不会对结果产生影响：冗余状态的初始值必须为0，这样从冗余态推导到可行态才会变成1 注意冗余态不要被赋初值为1即可 所以一开始不可以将dp数组初始化为0 */ #include<bits/stdc++.h> using namespace std; #define maxn 105 int n,a[maxn],dp[maxn][3][3]; int main(){ int t; cin>>t; for(int tt=1;tt<=t;tt++){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n); int ans=1; dp[1][0][1]=dp[1][1][0]=dp[1][1][2]=1; /*for(int i=2;i<=n;i++) for(int j=0;j<=2;j++) for(int k=0;k<=2;k++) dp[i][j][k]=1; */ for(int i=2;i<=n;i++){ for(int j=0;j<=2;j++){ if(j==0){//到i一次也没有改的情况 if(a[i]-a[i-1]<=2) dp[i][0][1]=dp[i-1][0][1]+1; else dp[i][0][1]=1; continue; } //剩下的是有改动的情况 for(int k=0;k<=2;k++){ dp[i][j][k]=1; for(int l=0;l<=2;l++){ int ai=a[i]-k+1,aj=a[i-1]-l+1;//两个数改动后的值 //不改动a[i]的情况 if(k==1){//这里不会出现冗余态：转移必定合法 if(a[i]-aj<=2) dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][l]+1);//注意：如果从不存在的状态推过来，就是0+1的形式 continue; } //改动a[i]的情况：这里会出现冗余态，dp[i-1][0][0|2]的状态是不存在的 if(ai-aj<=2) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][l]+1); } } } for(int j=0;j<=2;j++) for(int k=0;k<=2;k++) ans=max(ans,dp[i][j][k]); } printf("Case %d: %d ",tt,ans); } }