Codeforces 1083E. The Fair Nut and Rectangles (DP+Convex-Hull Trick)

日付: 12月 11, 2018

[Problem - 1083E - Codeforces](https://codeforces.com/contest/1083/problem/E)
## Problem
Given $n$ points $(x_i, y_i)$, each represents a rectangle $[(0,0), (0,y_i), (x_i,y_i), (x_i,0)]$ and no rectangles are nested. Each rectangle has a value $a_i$.

The task is to select some rectangles such that the unioned area minus sum of $a_i$ is maximum.

**Contraints:** $1\le n \le 10^6, \ 1\le x_i,y_i \le 10^9,\ 0\le a_i \le x_iy_i$

## Solution
First sort all rectangles by $x$. Let $f_i$ be the maximum result if the $i$-th rectangle is selected. Then the **state-transition equation** is: $$f_i = max\{f_j + y_i(x_i-x_j) - a_i | 0\le j < i\}$$

This is $O(n^2)$ but we can solve it in $O(n)$ by **convex-hull trick**.
 
 * Let $k < j < i$, where $i$ is the current processing index.
 * If $j$ is better than $k$ for transition to $i$, $\frac{f_j-f_k}{x_j-x_k} > y_i$, the left side is called *gradient* from $k$ to $j$, lets denote it by $G_{kj}$. We can prove that: If $G_{kj} < G_{ji}$, $j$ cannot be the best index for transition to $i$
 * Maintain a queue $Q$ of indexes that could be the best one for transition to $i$, make sure the gradients is not increasing (forming a convex hull). The best index is the last whose gradient is greater than $y_i$. (In this problem, $y_i$ is decreasing so that we can drop all indexes before the best one)

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

// CF. 1083E
const int N = 1e6 + 5;
struct State { int x, y; LL a; } S[N];
int n, hq = 0, tq = 1, Q[N];
LL ans = 0, F[N];

double slope(int j, int i) { return 1. * (F[i] - F[j]) / (S[i].x - S[j].x); }
LL calc(int j, int i) { return F[j] + 1LL * S[i].y * (S[i].x - S[j].x) - S[i].a; }

int main() {
    scanf("%d", &n);
    FI(i, 1, n) scanf("%d%d%lld", &S[i].x, &S[i].y, &S[i].a);
    sort(S + 1, S + 1 + n, [&](const auto & a, const auto & b) { return a.x < b.x; });
    FI(i, 1, n) {
        while (hq + 1 < tq && calc(Q[hq], i) < calc(Q[hq + 1], i)) hq++;
        F[i] = calc(Q[hq], i);
        ans = max(ans, F[i]);
        while (hq + 1 < tq && slope(Q[tq - 2], Q[tq - 1]) < slope(Q[tq - 1], i)) tq--;
        Q[tq++] = i;
    }
    printf("%lld\n", ans);
}
```

KONGROOの基地

このブログを検索

Codeforces 1083E. The Fair Nut and Rectangles (DP+Convex-Hull Trick)

コメント

コメントを投稿