求助,为何时间复杂度错误?
查看原帖
求助,为何时间复杂度错误?
620253
MvemiY楼主2023/11/15 21:25

思路是,设 fl,r,kf_{l,r,k} 表示区间 [l,r][l,r] 是否可以拼出 kk,fl,r,k=fl,mid,k−1&fmid+1,r,k−1f_{l,r,k} = f_{l,mid,k-1} \& f_{mid+1,r,k-1},时间复杂度 O(n3×Xw)O(\dfrac {n^3\times X}{w}) 应该可以过,但是 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;
}
2023/11/15 21:25
加载中...