题意

　　给定 n 个数，每一个数都是在 [1,m] 里的整数。

　　从中取出形如 {x,x,x} 或者 {x-1,x,x+1} 的集合，各个集合不能相交，问最多能取出几个。

　　$n,m\leq 10^6$

题解

　　标算非常简洁。

　　我这里讲讲我的做法，尽管相对复杂。

　　首先，我们可以忽略对于同一个 x ，取出大于2次 {x-1,x,x+1} 这种情况，因为这种可以用取 {x-1,x-1,x-1} {x,x,x} {x+1,x+1,x+1} 来代替。

　　所以一个x 最多被形如 {a-1,a,a+1} 的pair 取 6 次。即 {x-2,x-1,x}*2 , {x-1,x,x+1}*2 , {x,x+1,x+2}*2 。

　　现在来证明一个重要结论：

　　如果 x 的个数大于 7 ，那么至少可以取出一次 {x,x,x} 。（也就是说我们可以先不断取 {x,x,x} 这种pair，直到所有数字的出现次数都小于等于7）

　　设 t[x] 表示 x 的出现次数。

　　对于 t[x] = 8 的情况，考虑到它最多被形如 {a-1,a,a+1} 的这种pair取到6次，所以如果不取 {x,x,x} ，至少会多出2个。如果取了 {x,x,x} ，那么最多会影响一个形如 {a-1,a,a+1} 的pair，导致另外两个数不能取了，但是如果不取 {x,x,x} 也会多出两个，所以至少不亏。

　　对于 t[x]>8 的情况就更加显然了。

　　于是现在 t[x] < 8 。考虑 dp ，设 dp[i][j][k] 表示 [1,i] 中，i 被取了 j 次， i + 1 被取了 k 次，且 [1,i-1] 的数被取的次数没有超限， [i+2,m] 的数没有被取过，这种情况下取出的pair的最大个数。直接枚举转移暴力dp就好了。

　　时间复杂度 O(n) * 大常数。

　　实测可过。

代码

#include 
     
      using namespace std;typedef long long LL;LL read(){	LL x=0,f=0;	char ch=getchar();	while (!isdigit(ch))		f|=ch=='-',ch=getchar();	while (isdigit(ch))		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();	return f?-x:x;}const int N=1000005;int n,m;int t[N],ans=0;int dp[N][8][8];void ckmax(int &x,int y){	x=x>y?x:y;}int main(){	n=read(),m=read();	for (int i=1;i<=n;i++)		t[read()]++;	for (int i=1;i<=m;i++)		while (t[i]>7)			t[i]-=3,ans++;	for (int i=0;i<=m;i++)		for (int a=0;a<=7;a++)			for (int b=0;b<=7;b++)				dp[i][a][b]=-N*2;	dp[0][0][0]=0;	for (int i=0;i
      
       t[i]||b>t[i+1])					continue;				int v=dp[i][a][b];				for (int x=0;x<=2;x++)					for (int y=0;y<=2;y++)						if (a+x*3+y<=t[i]&&b+y<=t[i+1])							ckmax(dp[i+1][b+y][y],v+x+y);			}	int k=0;	for (int i=0;i<=t[m];i++)		ckmax(k,dp[m][i][0]+(t[m]-i)/3);	cout<

转载于:https://www.cnblogs.com/zhouzhendong/p/CF1110D.html

你可能感兴趣的文章