「Bzoj1597」「Luogu1010」土地购买

来源和评测点

Usaco2008 Mar Gold
Bzoj1597
Luoguc
Caioj1140

题目

「题目大意」
有N块长方形的土地,每块土地的价格是它的面积,但FJ可以同时购买多块土地。
这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换。
如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=25。
FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。
他需要你帮助他找到最小的经费。
「输入格式」
第1行一个整数N。
下来N行。第i+1行包含两个数,分别为第i块土地的长和宽。
「限定条件」
(1 <= N <= 50,000
每块土地的长宽满足1<=宽<=1,000,000;1<=长<=1,000,000)
「输出格式」
求最小的可行费用。
「输入样例」
4
100 1
15 15
20 5
1 100
「输出样例」
500
「样例解释」
FJ分3组买这些土地:
第一组:100×1,
第二组1×100,
第三组20×5 和 15×15。
每组的价格分别为100,100,300, 总共500

刷题记录

30min

分析

灰常妙的一点:
使用排序进行除杂(被完全覆盖的土地可以被忽略)
神奇的一幕出现了,可以实现长递增,宽递减(主要是题目特性)
于是就可以瞬间获得区间打包的费用!

想通这个以后接下来就甚至比上一题还简单了
部分省略

1.化简dp公式
a[i]=长 b[i]=宽
f[i]=min(f[j]+a[i]*b[j+1])

2.证明决策单调性
假设j1<j2<i
已知对于i,j2优于j1,本题追求小,所以
假设f[j2]+a[i]*b[j2+1]<=f[j1]+a[i]*b[j1+1]——————-①
是否f[j2]+a[t]*b[j2+1]<=f[j1]+a[t]*b[j1+1]——————-②
为了从①证明②,两式取差
得证
所以这次如果选了j2,j1将没有任何用处,可淘汰

3.确定比较状态优劣的斜率方程
只能用于相邻的状态比较
斜率=(y1-y2)/(x1-x2)

f[j2]+a[i]*b[j2+1]<=f[j1]+a[i]*b[j1+1]
(f[j2]-f[j1])/(b[j1+1]-b[j2+1])<=a[i]
满足则j2更优

那么把状态变成点( b[j],f[j] )

4.单调队列维护
满足: 相邻斜率不递减
故形状为一个向下的凸壳(形如丿字)

一、去头(两者比较)
将a[]理解为i给出的标杆,假如“头与头后一个斜率”小于标杆,
意味着后一个更优秀,将头剔除

二、继承
从当前最优秀的头继承

三、铺垫与维护(三者比较)
将当前状态放入队列,并两两比较删除无用状态,保证相邻斜率不递减
删除正确性证明:
对于a和b的斜率x<=b和c的斜率y
被删除的末尾,在(末尾前一个,末尾,当前状态)中必定不是最优状态,
因为斜率必定不如他们
哪怕是这种极端情况:
○ ○

斜率越大,则越靠近标杆,也就意味着后面这个越优秀
(虽然在小于标杆的时候依然是前面的优秀,
但我这里的意思是同样的前者下,后者1会比后者2更优秀)
斜率为0意味着同样优秀,那么当然是后面的更好了
总而言之,斜率越小越优秀

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量*******************
const int MAXN=51000;
//*******************全局定义*******************
struct nod
{
double a,b;
}p[MAXN];
bool cmp(nod a,nod b)
{
return (a.a<b.a) or (a.a==b.a and a.b<b.b);
}
double f[MAXN];
//*******************实现*******************
double X(int x)
{
return p[x].b;
}
double Y(int x)
{
return f[x];
}
double slop(int x,int y)
{
return ( Y(y)-Y(x) )/( X(x+1)-X(y+1) );
}
int tp;
int g[MAXN];
void solve()
{
int tou=1,wei=1;
for(int i=1;i<=tp;i++)
{
while(tou<wei and slop(g[tou+1],g[tou])<=p[i].a) tou++;
int j=g[tou];
f[i]=f[j]+p[i].a*p[j+1].b;
while(tou<wei and slop(g[wei-1],g[wei])>=slop(g[wei],i)) wei--;
g[++wei]=i;
}
}
//*******************主函数*******************
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].a,&p[i].b);
sort(p+1,p+1+n,cmp);
tp=1;
for(int i=2;i<=n;i++)
{
while(tp>0 and p[tp].b<=p[i].b) tp--;
p[++tp]=p[i];
}
solve();
printf("%.0lf",f[tp]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c717.html
转载请注明出处,谢谢!