Jongmah CodeForces - 1110D

传送门

题意：你有n个数字，范围[1, m]，你可以选择其中的三个数字构成一个三元组，但是这三个数字必须是连续的或者相同的，每个数字只能用一次，问这n个数字最多构成多少个三元组?

题解：三个一模一样的顺子等于三个对子（三张）

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<map>

#include<cstdlib>

#include<vector>

#include<string>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

const double PI = acos(-1.0);

const int maxn =  1e6+;

const int mod = 1e9+;

int a[maxn],cnt[maxn];

int dp[maxn][][];  //dp[j][j][k]表示数字1-i,有j个(i-1,i,i+1),有k个(i,i+1,i+2)

int main()

{

    int n,m;

    scanf("%d %d",&n,&m);

    for(int i=;i<=n;i++) {

        scanf("%d", &a[i]);

        cnt[a[i]]++;

    }

    memset(dp,-INF,sizeof dp);

    dp[][][] = ;

    for(int i=;i<=m+;i++){

        for(int j=;j<;j++){

            for(int k=;k<;k++){

                if(dp[i][j][k] < )

                    continue;

                int now = cnt[i+]-j-k;   //前面有j个(i-1,i,i+1)和k个(i,i+1,i+2),现在有cnt[i+1]个i+1,可以形成cnt[i+1]-j-k个新的三元组

                for(int t=;t< && t<=now;t++){

                    dp[i+][k][t] = max(dp[i+][k][t],dp[i][j][k] + (now - t) /  + t);

                }

            }

        }

    }

    printf("%d\n",dp[m+][][]);

}