题解 CF1110D 【Jongmah】

其实主要思想都差不多，但我发这篇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，如是做细节少、思考难度小）

然后我们的代码特别短:

#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