Vladik and cards CodeForces - 743E (状压)

时间：2021-12-30 01:55:02

大意: 给定序列, 求选出一个最长的子序列, 使得任选两个[1,8]的数字, 在子序列中的出现次数差不超过1, 且子序列中相同数字连续.

正解是状压dp, 先二分转为判断[1,8]出现次数>=x是否成立, 再dp求出前i位匹配状态S长度为x+1的数字个数的最大值, 特判一下最低次数为0的情况. 这题打了好久, 太菜了.......

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef bitset<10> btc;

const int P = 1e9+7, INF = 0xbcbcbcbc;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

//head

const int N = 1e3+10, S = (1<<8)-1;

int n, ans;

int a[N], dp[N][S+1], dig[S+1], f[N][N][9], g[S+1];

void chkmax(int &x, int y) {x=max(x,y);}

void chkmin(int &x, int y) {x=min(x,y);}

int chk(int x) {

	memset(dp, 0xbc, sizeof dp);

	dp[0][0] = 0;

	REP(i,1,n) REP(j,0,S-1) if (dp[i-1][j]!=INF) {

		for (int k=~j&S, t; k; k^=t) {

			t = k&-k;

			int p1 = f[i][x][dig[t]], p2 = f[i][x+1][dig[t]];

			if (p1<=n) chkmax(dp[p1][j^t], dp[i-1][j]);

			if (p2<=n) chkmax(dp[p2][j^t], dp[i-1][j]+1);

		}

	}

	int r = INF;

	REP(i,1,n) chkmax(r,dp[i][S]);

	ans = max(ans, r+8*x);

	return r!=INF;

}

int main() {

	REP(i,0,7) dig[1<<i]=i+1;

	scanf("%d", &n);

	REP(i,1,n) scanf("%d", a+i);

	memset(f,0x3f,sizeof f);

	PER(i,1,n) REP(j,1,n) REP(k,1,8) {

		if (a[i]==k) f[i][1][k]=i,f[i][j][k]=f[i+1][j-1][k];

		else chkmin(f[i][j][k],f[i+1][j][k]);

	}

	g[0] = 1;

	REP(i,1,n) REP(j,0,S) if (!(j>>a[i]-1&1)) {

		g[j^1<<a[i]-1] |= g[j];

	}

	REP(i,0,S) if (g[i]) ans=max(ans,__builtin_popcount(i));

	int l=1, r=n/8;

	while (l<=r) {

		if (chk(mid)) l=mid+1;

		else r=mid-1;

	}

	printf("%d\n", ans);

}

相关文章