思路是,设 fl,r,k 表示区间 [l,r] 是否可以拼出 k,fl,r,k=fl,mid,k−1&fmid+1,r,k−1,时间复杂度 O(wn3×X) 应该可以过,但是 T 飞了,为啥?
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 305;
bitset <65> f[MAXN][MAXN];
int n, a[MAXN];
int main(){
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++)
cin >> a[i], f[i][i][a[i]] = 1, ans = max(ans, a[i]);
for(int len = 2; len <= n; len++){
for(int k = 2; k <= 60; k++){
bool flag = 0;
for(int l = 1, r = l + len - 1; r <= n; l++, r++){
for(int mm = l; mm <= r && !f[l][r][k]; mm++)
f[l][r][k] = (f[l][mm][k-1] && f[mm+1][r][k-1]);
if(f[l][r][k])
ans = max(ans, k);
}
}
}
cout << ans;
return 0;
}