1 条题解
-
1赵青海 (huhe) LV 7 SU @ 2021-10-7 14:26:35
#include <iostream> #include <cstring> using namespace std; const int N = 210; int f[N][N][N]; int len[N], a[N]; int arr[N]; int n; // 1 1 2 2 3 3 1 1 3 3 2 2 2 2 2 // 2 2 2 2 2 5 len // 1 2 3 1 1 2 a int init() { int j = 0; for(int i = 0 ; i <= n ; i ++) { if(i == 0) { len[j] = 1; a[j] = arr[i]; }else if(arr[i] == arr[i - 1]){ len[j] ++; }else{ j ++; len[j] = 1; a[j] = arr[i]; } } return j; // len的长度 } int dfs(int l, int r, int k) { if(l > r) return f[l][r][k] = -100000; //不可能成立的情况 if(l == r) return f[l][r][k] = (len[r] + k) * (len[r] + k); //相当于循环写的初始化 if(~f[l][r][k]) // 记忆话部分 return f[l][r][k]; int res = dfs(l, r - 1, 0) + (len[r] + k) * (len[r] + k); // 最后一个算一下 for(int i = l ; i < r ; i ++) // 枚举分割方法 { if(a[i] == a[r]) res = max(res, dfs(i + 1, r - 1, 0) + dfs(l, i, len[r] + k)); } return f[l][r][k] = res; } int main() { int T; cin >> T; for(int t = 1 ; t <= T ; t ++) { cin >> n; for(int i = 0 ; i < n ; i ++) cin >> arr[i]; n = init(); // 压缩 memset(f, -1, sizeof f); cout << "Case " << t << ": " << dfs(0, n - 1, 0) << endl; } return 0; }
- 1
信息
- ID
- 232
- 时间
- 1500ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 16
- 已通过
- 6
- 上传者