Solution. LG5244 [USACO19FEB] Mowing Mischief P
Description 展开目录
在
Solution 展开目录
首先要做一个二维 LIS,按横坐标排序后用树状数组维护转移即可。这部分是平凡的。
按照以每个点结尾的最长 LIS 长度分层,第二问的转移都应当发生在相邻层之间,这样我们就有了一个
接下来考虑优化。由于涉及到正方形面积,很容易让人想到决策单调性。
对于同层的点,如果我们将其按横坐标从小到大排序,纵坐标一定单调减。考虑第
两式联立化简后,问题转化为判断
中间的计算过程不多赘述,也很推荐通过画图来理解这一不等式,更加直观,只不过用电脑画个好看的图放题解里太麻烦 。
这是反向的四边形不等式,故本题有递减的决策单调性(link),常规的做法是用二分栈来维护决策点,或者由于分层转移的特性,我们也可以使用分治,但本题中由于每个决策点只能向一个区间进行转移,直接应用这两种方法都行不通。
对于二分栈来说,我们可能会想在到达某个决策点作用域左端点时将其插入单调栈,但问题在于,此时这个决策点可能是劣的,无法替代栈顶,但这并不意味着这个决策点就可以被舍弃,因为其可能拥有比栈顶更大的作用域,可以在离开栈顶作用域后入栈,如果对一个决策点多次尝试入栈,时间复杂度就难以保证了。
对于分治也存在类似的问题,我们无法直接将决策点一分为二,分配给左右两侧的 dp 数组。
于是,我们不得不付出一个
每个线段树结点都应视作一个子问题,所以应在 dp 值算出后再进行合并,否则可能会出现在另一个结点上做出的决策优于当前结点上的所有决策点,导致当前结点无法转移的问题。
值得一提的是,我们需要线段树分治的本质原因在于决策单调性和可转移区间的移动方向不一致,如果移动方向一致的话,例如本题如果改为最大化面积,决策单调性变为递增,则直接使用二分队列或分治都是没有问题的。
Code 展开目录
- namespace Main{
- const int N = 200005;
- const int V = 1000005;
- int n, t, f[N];
- pair<int, int> flower[N];
- vector<pair<int, int>> layer[N];
- vector<ll> dp[N];
- struct bit{
- int t[V];
- inline int lowbit(int x) { return x & -x; }
- void modify(int x, int k) { for(; x < V; x += lowbit(x)) t[x] = max(t[x], k); }
- int query(int x) { int res = 0; for(; x; x -= lowbit(x)) res = max(res, t[x]); return res; }
- }tree;
- struct segtree{
- struct segtree_node{
- int l, r;
- vector<int> trans;
- }t[N<<2];
- #define ls p<<1
- #define rs p<<1|1
- void build(int p, int l, int r){
- t[p].l = l, t[p].r = r, t[p].trans.clear();
- if(l == r) return;
- int mid = l + r >> 1;
- build(ls, l, mid), build(rs, mid + 1, r);
- }
- void add(int p, int l, int r, int k){
- if(t[p].l >= l && t[p].r <= r){
- t[p].trans.push_back(k);
- return;
- }
- int mid = t[p].l + t[p].r >> 1;
- if(mid >= l) add(ls, l, r, k);
- if(mid < r) add(rs, l, r, k);
- }
- void calc(int d, vector<int> &sp, int l, int r, int sl, int sr){
- if(l > r) return;
- int mid = l + r >> 1, s = -1;
- ll val = 1e18;
- for(int i = sl; i <= sr; i++){
- ll tmp = dp[d - 1][sp[i]] + 1ll * (layer[d][mid].first - layer[d - 1][sp[i]].first) * (layer[d][mid].second - layer[d - 1][sp[i]].second);
- if(tmp < val) { val = tmp; s = i; }
- }
- dp[d][mid] = min(dp[d][mid], val);
- calc(d, sp, l, mid - 1, s, sr), calc(d, sp, mid + 1, r, sl, s);
- }
- void solve(int p, int d){
- if(!t[p].trans.empty()) calc(d, t[p].trans, t[p].l, t[p].r, 0, t[p].trans.size() - 1);
- if(t[p].l == t[p].r) return;
- solve(ls, d), solve(rs, d);
- }
- #undef ls
- #undef rs
- }t2;
- void Main(){
- input(n, t);
- for(int i = 0; i < n; i++) input(flower[i].first, flower[i].second);
- sort(flower, flower + n);
- int mx = 0;
- for(int i = 0; i < n; i++){
- f[i] = tree.query(flower[i].second) + 1;
- tree.modify(flower[i].second, f[i]);
- layer[f[i]].push_back(flower[i]);
- mx = max(mx, f[i]);
- }
- layer[0].emplace_back(0, 0), layer[++mx].emplace_back(t, t);
- dp[0] = {0};
- for(int i = 1; i <= mx; i++){
- t2.build(1, 0, layer[i].size() - 1);
- dp[i].resize(layer[i].size(), 1e18);
- for(int j = 0; j < layer[i - 1].size(); j++){
- int l = lower_bound(layer[i].begin(), layer[i].end(), layer[i - 1][j]) - layer[i].begin();
- int r = lower_bound(layer[i].begin(), layer[i].end(), layer[i - 1][j], [](pair<int, int> a, pair<int, int> b){
- return a.second > b.second;
- }) - layer[i].begin() - 1;
- if(l <= r) t2.add(1, l, r, j);
- }
- t2.solve(1, i);
- }
- write(dp[mx][0]);
- return;
- }
- } // namespace Main
本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。