ZR杂题选讲10.6

杂一

突然发现这题我写了三个小时...

错点从主函数开始数起：

• 1.预处理的时候，因为是要求往后多少个，所以循环应该倒着枚举（一开始正着竟然还过了样例）
• 2.二分的边界应该有0，因为可以有些选有些不选。（不得不说样例还挺良心的）。(check)得时候也要特判一下这种情况，因为选的长度是1的话就不用每种元素都选了，有不选的元素也是合法的。
• 3.因为位运算不熟练被卡了好久。分清&和|。
• 4关于初始化，不能全赋值成0。因为在开始的时候，有些位置是不合法的。换个说法，只能从(dp[1][0])开始转移（(dp[i][j])表示用前(i-1)位置的数，处理好的颜色集合是(j)的最长长度）
• 5.全集是(1<<8)-1，不是(1<<9)-1。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1005;
int n,a[N],dp[N][300],ans,net[N][N];
int book[10];
bool check(int l)
{
	memset(dp,128,sizeof(dp));
	int S=(1<<8)-1;
	dp[1][0]=0;
	for(int i=1;i<=n+1;i++)
	{
		for(int j=0;j<=S;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j]);
			if(!(j&(1<<(a[i]-1))))
			{
                if(net[i][l-1]<=n&&net[i][l-1]>0)
				 dp[net[i][l-1]+1][j+(1<<(a[i]-1))]=max(dp[net[i][l-1]+1][j+(1<<(a[i]-1))],dp[i][j]+l);
				if(net[i][l]<=n&&net[i][l]>0)
				 dp[net[i][l]+1][j+(1<<(a[i]-1))]=max(dp[net[i][l]+1][j+(1<<(a[i]-1))],dp[i][j]+l+1);
			}
		} 
	}
	if(l==0)
	{
		for(int i=0;i<=S;i++)
		 ans=max(ans,dp[n+1][i]);
		return true;
	}
	ans=max(ans,dp[n+1][S]); 
	if(dp[n+1][S]>0) return true;
	return false;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	for(int i=1;i<=8;i++)
	 book[i]=n+1;
	for(int i=n;i>=1;i--)
	{
		net[i][0]=i;
		net[i][1]=book[a[i]];
		book[a[i]]=i;
	}
	for(int i=2;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  net[j][i]=net[net[j][i-1]][1];
	int l=0,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	printf("%d
",ans);
	return 0;
}