题意

给定一个长 $n$ 的序列 $a_i$ ，可以进行操作，每次操作选区间 $[l,r]$ ，条件是 $\wedge_{i=l}^{r}~a_i=0$ ，操作完会删除 $[l,r]$ 。问最多操作次数。

$n,a_i\lt64$ 。

题解

区间 DP。设 $f_{l,r}$ 表示若区间 $[l,r]$ 可以合法，它的最大值，考虑 $l<k_1\leq k_2<r$ ，是 $f_{k_1,k_2}$ 搞完后搞 $f_{l,r}$ 。做完再扫一遍。

$\mathcal{O}(n^4)$ 。

代码

挂了。

const int N = 70;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int a[N];
	int f[N][N], g[N];
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int l = 1; l <= n; l++) {
			int val = a[l];
			for (int r = l; r <= n; r++) {
				val &= a[r];
				if (!val) f[l][r] = 1;
			}
		}
		for (int len = 3; len <= n; len++) {
			for (int l = 1; l + len - 1 <= n; l++) {
				int r = l + len - 1;
				int val1 = a[l];
				for (int k1 = l + 1; k1 <= r; val1 &= a[k1], k1++) {
					int val2 = a[r];
					for (int k2 = r - 1; k2 >= k1; val2 &= a[k2], k2--) {
						if (!f[k1][k2] || (val1 & val2)) continue;
						if (!val1 && !val2) f[l][r] = max(f[l][r], f[k1][k2] + 2);
						else f[l][r] = max(f[l][r], f[k1][k2] + 1);
					}
				}
			}
		}
//		for (int len = 1; len <= n; len++)
//			for (int l = 1; l <= n; l++)
//				printf("%d\t%d\t%d\n", l, len + l - 1, f[l][l + len - 1]);
		for (int i = 1; i <= n; i++) {
			for (int l = i; l; l--) {
				for (int r = l; r <= i; r++) {
					for (int j = l - 1; j >= 0; j--) {
						g[i] = max(g[i], g[j] + f[l][r]);
					}
				}
			}
		}
		printf ("%d\n", g[n]);
		return 0;
	}
}

int main () {
//	freopen("ex_eat4.in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}