Codeforces 1110D (DP)

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)$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, m, cnt[1000000 + 5];
    LL dp[1000000 + 5][3][3];

    void clean() {
        ms(dp, -1);
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (LL x, i = 1; i <= n; ++i) scanf("%lld", &x), ++cnt[x];

        dp[0][0][0] = 0;
        for (LL i = 1; i <= m; ++i) {
            for (LL a = 0; a < 3; ++a) {
                for (LL b = 0; b < 3; ++b) {
                    for (LL c = 0; c < 3; ++c) {
                        LL tmp = cnt[i] - a - b - c;
                        if (tmp >= 0 && dp[i - 1][b][c] >= 0) {
                            dp[i][a][b] = max(dp[i][a][b], dp[i - 1][b][c] + c + tmp / 3);
                        }
                    }
                }
            }
        }

        LL ans = 0;
        for (LL a = 0; a < 3; ++a) 
        for (LL b = 0; b < 3; ++b) ans = max(ans, dp[m][a][b]);

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}