/*
先将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\n",tt,ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10503893.html
