什么是网站框架结构,做网站协议书,免费手机网站源码,外贸seo推广公司题意
传送门 LeeCode 546 移除盒子
题解
难以顺序处理#xff0c;故考虑不断拓展区间。令 d p l , r dp_{l, r} dpl,r 为 [ l , r ) [l,r) [l,r) 的答案#xff0c;当 b l b_{l} bl 与 b r − 1 b_{r-1} br−1 不在同一轮被移除#xff0c;则可以枚举分界点更新…题意
传送门 LeeCode 546 移除盒子
题解
难以顺序处理故考虑不断拓展区间。令 d p l , r dp_{l, r} dpl,r 为 [ l , r ) [l,r) [l,r) 的答案当 b l b_{l} bl 与 b r − 1 b_{r-1} br−1 不在同一轮被移除则可以枚举分界点更新答案反之则难以直接递推。令 f l , r , k f_{l,r,k} fl,r,k 为 [ l , r ) [l, r) [l,r) 中与 b l b_{l} bl 在同一轮被移除的元素数量即可。总时间复杂度 O ( n 4 ) O(n^4) O(n4)。
#include bits/stdc.h
using namespace std;constexpr int N 100;
class Solution {public:int f[N][N 1][N 1], dp[N][N 1];int removeBoxes(vectorint boxes) {int n boxes.size();const int inf 1e9;for (int i 0; i n; i) {for (int j 0; j n; j) {dp[i][j] -inf;for (int k 0; k n; k) {f[i][j][k] -inf;}}}for (int i 0; i n; i) {f[i][i 1][1] 0;dp[i][i 1] 1;}auto get_max [](int x, int y) {x max(x, y);};for (int w 2; w n; w) {for (int l 0; l w n; l) {int r l w;for (int k 1; k r - l; k) {if (boxes[l] boxes[r - 1]) {get_max(f[l][r][k], f[l][r - 1][k - 1]);}for (int m l 1; m r; m) {get_max(f[l][r][k], f[l][m][k] dp[m][r]);}get_max(dp[l][r], f[l][r][k] k * k);}}}return dp[0][n];}
};
