$dp.$
其实主要思想都差不多,但我发这篇$sol$为了阐明一种观点:复杂度同阶的$DP$,不同的状态设计,会导致代码难度、时空复杂度等截然不同。
我们定义状态$dp_{i,j_{1},j_{2}}$表示考虑了前$i$大序号的麻将($mahJong$),其中有$j_{1}$个$[i - 1, i, i + 1]$类型、有$j_{2}$个$[i, i + 1, i + 2]$类型的组合,最多组成多少个三元组。
这样定义状态的原因是:我们发现如果单纯用$1$维状态转移,那么状态势必是“前$i$大序号的麻将包含的三元组个数”,但是此状态不明确——无法准确定义“包含”的意思。而此处我们定义包含指**三元组右端点也$\leq i$**,那么$[i - 1, i, i + 1]$和$[i, i + 1, i + 2]$便需要单独定义出来。
转移的时候直接枚举有多少个$[i + 1,i+2, i+3]$即可(因为我们使用$i$更新$i+1$而不是用$i-1$更新$i$,如是做细节少、思考难度小)
然后我们的代码特别短:
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 1000020
using namespace std ; int N, M ;
int Sum[MAXN], dp[MAXN][3][3], i, j, k, l ;
inline int qrd(){
register int k = 0 ; char c = getchar() ;
while (c < '0' || c > '9') c = getchar() ;
while (c <= '9' && c >= '0') k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k ;
}
int main(){
cin >> N >> M ;
memset(dp, -1, sizeof(dp)), dp[0][0][0] = 0 ;
for (i = 1 ; i <= N ; ++ i) Sum[ qrd() ] ++ ;
for (i = 1 ; i <= M ; ++ i){
for (j = 0 ; j < 3 ; ++ j)
for (k = 0 ; k < 3 ; ++ k)
for (l = 0 ; l < 3 ; ++ l)
if (Sum[i] < j + k + l) continue ;
else dp[i][k][l] = max(dp[i][k][l], dp[i - 1][j][k] + (Sum[i] - j - k - l)/3 + l) ;
}
cout << dp[M][0][0] << endl ; return 0 ;
}
```
闲扯一点:这个题楼主在当时并没有能够想出来……因为没有深刻思考其中的性质qaq