Codeforces 1106E
题意:给定一个$n$长值域为$m$的序列,你要将其组成尽可能多的三元组$(a, b, c)$满足$a=b=c$或者$b=a+1,c=b+1$。
一开始读错题了。
先将所有数存在一个桶里,按数大小来DP。
显然对于一种方案$(a,b,c)$,他只会重复至多$2$次。
那么对于一个方案$(i,i+1,i+2)$,他最多只会有$2$个
那么设$dp(i,0/1/2,0/1/2)$为前$i$个数,第一个数是$i$的三元组个数,第二个数是$i$的三元组个数的最大个数。
转移
$$
dp(i,a,b)=\max_{0\leq c \leq 2}(dp(i-1,b,c)+c+(cnt-a-b-c) / 3)
$$
其中$cnt$为$i$数的个数。
后面$(cnt-a-b-c) / 3)$等价于将多余的$i$组成三元组$(i,i,i)$