为什么记搜TLE
查看原帖
为什么记搜TLE
305002
vegetable_ste楼主2021/8/24 21:28

这是在逼迫我考虑循环顺序吗。。。

#include <bits/stdc++.h>
using namespace std;
const int N = 300;
int n, a[N], dp[N][N];
// 这里考虑只转移能够合并的
int solve(int L, int R) {
	if(dp[L][R]) return dp[L][R];
	if(L == R) return a[L];
	int res = 0;
	for(int i = L; i < R; i ++ ) {
		int s1 = solve(L, i), s2 = solve(i + 1, R);
		if(!s1 || !s2) continue;
		if(s1 == s2) res = max(res, s1 + 1);
	}
	return dp[L][R] = res;
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++ ) cin >> a[i];
	int res = 0;
	solve(1, n);
	for(int i = 1; i <= n; i ++ )
		for(int j = i; j <= n; j ++ ) {
			res = max(res, dp[i][j]);
			#ifdef debug
			cout << "[" << i << ", " << j << "]: " << solve(i, j) << endl;
			#endif
		}
	cout << res << endl;
	return 0;
}

2021/8/24 21:28
加载中...