题意

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

分析

根据官方Editorial的说法，似乎没有一个真正正确的贪心（但是说不定就有人乱搞出来了）。这里用dp来解决问题。

这种dp题目我没做过，这次涨姿势了。首先要搞明白一个事实：我们完全可以保证构建一个最优解，其中连续的三元组对于每个数不会出现超过两个——因为如果出现超过三个，就可以拆分成三个相同组。在这样的前提下，我们就可以构建状态了。

进一步思考状态怎么得到的。对于第i个数，与之的相关的顺子有\([i-2,i-1,i],[i-1,i,i+1],[i,i+1,i+2]\)，而全考虑是不必要的，重复了。选择两种状态考虑转移即可，这里考虑\([i-1,i,i+1]\)和\([i,i+1,i+2]\)。

暴力枚举他们分别有几种可能的情况（前面说了只有0，1，2三种情况），然后考虑转移，它们如何从i移动到i+1为center？那得看有几个i+1：记\(dp[i][j][k]\)为前i个数有j个第一种顺子和k种第二个顺子，那么就会剩下\(cnt[i+1]-j-k\)个i+1。我们不去考虑后面的i+2，i+3到底存不存在（因为如果不存在，后面推导的时候将只会更新j=0，k=0的情况），直接思考这些i+1分别会产生多少种顺子——暴力枚举产生0，1，2种连顺子（\([i+1,i+2,i+3]\)）即可。这样就能写出具体的状态转移方程了。具体见代码。

这样一来，这题就能得到解决。如果内存要求苛刻，可以使用滚动数组解决（提示：计算结果用到的结果并不多）。

代码

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

const int MAXN = 100005;

int cnt[MAXN], dp[MAXN][3][3];

int main()

{

	int n,m; cin>>n>>m;

	ZERO(cnt);

	rep(i,1,n)

	{

		int tmp; cin>>tmp;

		cnt[tmp]++;

	}

	MS(dp, -1);

	dp[0][0][0]=0;

	rep(i,0,m+1)

	{

		rep(j,0,2)

		{

			rep(k,0,2)

			{

				if(dp[i][j][k]<0) continue;

				int now=cnt[i+1]-j-k;

				for(int t=0; t<=2 && t<=now; ++t)

				{

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

				}

			}

		}

	}

	cout<<dp[m+1][0][0]<<endl;

	return 0;

}

巴特西

「日常训练」Jongmah（Codeforces-1110D）

题意

分析

代码

最新文章

热门文章