CF 1110 D. Jongmah

D. Jongmah

链接

题意：

　　一些数字，有两种方式组成一个三元组，[x,x,x]，[x,x+1,x+2]，每个数字只能用一次，求最多组成多少三元组。

分析：

　　因为每三个[x,x+1,x+2]是可以拆成[x,x,x]，[x+1,x+1,x+1]，[x+2,x+2,x+2]的，所以可以认为对于以x开始的[x,x+1,x+2]最多有两个。

　　于是可以dp[i][x][y]表示到第i个数字，存在x个[i-1,i,i+1]，y个[i,i+1,i+2]，最多组成多少个三元组（这些三元组的右端点在i以内，超出i三元组有x+y个，没有记录到里面）

　　然后转移的时候枚举多少个[i+1,i+2,i+3]。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = 1e6 + ;

LL f[N][][], a[N];

int main() {

    int n = read(), m = read();

    for (int i = ; i <= n; ++i) a[read()] ++;

    memset(f, -0x3f, sizeof(f));

    f[][][] = ;

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

        for (int x = ; x < ; ++x)

            for (int y = ; y < ; ++y)

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

                    if (a[i] < x + y + z) continue;

                    f[i][x][y] = max(f[i][x][y], f[i - ][z][x] + (a[i] - x - y - z) /  + z);

                }

    }

    cout << f[m][][];

    return ;

}