P2900 [USACO08MAR] Land Acquisition G
思路:
先将土地按照长\(H\)排序
从后往前遍历如果有出现\(H[i] \le H[j]\ \text{and}\ W[i] \le W[j]\)则这块土地是没有贡献的(\(i\)与\(j\)拼单)
处理完之后H从小到大有序, W从大到小有序
方程:
\(f[i] = f[j - 1] + max(h[k]) * max(w[k]) (k∈[j, i])\)
等价于
\(f[i] = f[j - 1] + h[i] * w[j];\)
将式子变成
\(f[j - 1] = -h[i] * w[j] + f[i];\)
\(y = k x + b\)
\(f[j - 1]\) 表示 \(y\)
$-h[i] $表示 \(k\)(斜率)
\(w[j]\)表示\(x\)
\(f[i]\)表示\(b\)
解题步骤:
- 算出\(x, y\)
- 用单调队列维护下凸包
拿队尾两个元素组成线段的斜率与\(i\)和队尾的元素组成的线段的斜率比较
如果\(i\)和队尾的元素组成的线段的斜率大,则出队
bool check(int i, int j, int k) // i是最右边的点,j是队列倒数第二个点,k是队尾
{
return (y[k] - y[j]) * (x[i] - x[k]) <= (y[i] - y[k]) * (x[k] - x[j]);
}
- 入队
- 比较队首元素和队首第二个元素分别与 \(i\)算出的值进行比较
若队首元素算出的值不优于队首第二个元素的值,则出队
while (hd < tl && clac(i, q[hd]) >= clac(i, q[hd + 1]))
++hd;
- 算出\(\text{dp}\)的值
代码:
无优化\(\text{dp}\):
#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 5e4 + 5;
int n, f[N], vis[N], len;
struct Node
{
int h, w;
friend bool operator< (Node x, Node y)
{
if (x.h != y.h) return x.h < y.h;
return x.w > y.w;
}
}a[N], b[N];
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &a[i].h, &a[i].w);
sort(a + 1, a + 1 + n);
int maxx = 0;
for (int i = n; i >= 1; --i)
{
if (maxx >= a[i].w) vis[i] = 1;
maxx = max(maxx, a[i].w);
}
for (int i = 1; i <= n; ++i)
if (!vis[i]) b[++len] = a[i];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= len; ++i)
for (int j = 0; j < i; ++j)
f[i] = min(f[i], f[j] + b[i].h * b[j + 1].w);
printf("%lld", f[len]);
return 0;
}
正解:
#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 5e4 + 5;
int n, m, f[N], vis[N], q[N], hd, tl, x[N], y[N];
struct Node
{
int h, w;
friend bool operator< (Node x, Node y)
{
if (x.h != y.h) return x.h < y.h;
return x.w > y.w;
}
}a[N], b[N];
int clac(int i, int j)
{ return f[j - 1] + b[i].h * b[j].w; }
bool check(int i, int j, int k)
{ return (y[k] - y[j]) * (x[i] - x[k]) <= (y[i] - y[k]) * (x[k] - x[j]); }
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld%lld", &a[i].h, &a[i].w);
sort(a + 1, a + 1 + n);
int maxx = 0;
for (int i = n; i >= 1; --i)
{
if (maxx >= a[i].w) vis[i] = 1;
maxx = max(maxx, a[i].w);
}
for (int i = 1; i <= n; ++i)
if (!vis[i]) b[++m] = a[i];
memset(f, 0x3f, sizeof f);
f[0] = 0;
hd = 1, tl = 0;
for (int i = 1; i <= m; ++i)
{
x[i] = b[i].w, y[i] = f[i - 1];
while (hd < tl && check(i, q[tl - 1], q[tl])) --tl;
q[++tl] = i;
while (hd < tl && clac(i, q[hd]) >= clac(i, q[hd + 1])) ++hd;
f[i] = clac(i, q[hd]);
}
printf("%lld\n", f[m]);
return 0;
}
标签:Node,maxx,Land,return,int,clac,P2900,Acquisition,hd
From: https://www.cnblogs.com/wanghaoze121126/p/18331194