The Fair Nut and Rectangles

题意:有n个矩形,然后你可以选择k个矩形,选择一个矩形需要支付代价 ai, 问 总面积- 总支付代价 最大能是多少, 保证没有矩形套矩形。

题解:

sort 一下 只有  x 会递增  y 递减

然后 f[i] = f[j] + (x[i]-x[j])*y[i] - a[i]

f[j] = f[i] - x[i] * y[i] + x[j] * y[i] + a[i]

即 y = f[j], x = x[j], k = y[i],  b = f[i] - x[i] * y[i] + a[i]

我们需要维护 f[i] 尽可能大, 所以我们维护一个上突壳就好了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e6 + ;
struct Node{
int x, y;
LL a;
bool operator < (const Node & z) const{
return x < z.x;
}
}A[N];
LL f[N];
int q[N];
int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%d%d%lld", &A[i].x, &A[i].y, &A[i].a);
sort(A+, A++n);
int L = , R = ;
for(int i = ; i <= n; ++i){
while(L < R && f[q[L+]]-f[q[L]]>= 1ll*A[i].y * ((A[q[L+]].x - A[q[L]].x))) ++L;
f[i] = f[q[L]] + (1ll*A[i].x-A[q[L]].x)*A[i].y - A[i].a;
while(L < R && ((long double)f[q[R]]-f[q[R-]]) * (A[i].x - A[q[R]].x) <= ((long double)f[i]-f[q[R]]) * ((A[q[R]].x - A[q[R-]].x))) --R;
q[++R] = i;
}
LL ans = ;
for(int i = ; i <= n; ++i) ans = max(ans, f[i]);
cout << ans << endl;
return ;
}

最新文章

  1. Android Studio Lambda Config
  2. HDU1502/Luogu1352/UVa1220 party[树形DP]
  3. VTK初学一,b_PolyVertex多个图形点的绘制
  4. OAF与Windows 7版本不兼容黑屏卡顿问题
  5. mongodb地理位置索引
  6. C# #define
  7. ImageMagick提取图像原始数据(ImageData/RawData)
  8. ArcEngine 添加字段
  9. bzoj1632 [Usaco2007 Feb]Lilypad Pond
  10. 解决linux top命令提示的unknown terminal type的问题
  11. margin重叠
  12. 【京东账户】——Mysql/PHP/Ajax爬坑之页头页尾加载
  13. Scrapy1.4爬取笑话网站数据,Python3.5+Django2.0构建笑话应用
  14. regression and anova
  15. 【SVN】关于钩子的一些使用
  16. hive数据导出到本地目录 抛异常
  17. (后端)Java中关于金额大小写的工具类
  18. 查看Java JVM参数配置信息命令
  19. Python中 __init__的通俗解释?附修饰器contextmanager的理解
  20. Java – How to get current date time

热门文章

  1. 准时制生产(Just in Time,JIT)
  2. Usaco Training [2.1] The Castle 搜索
  3. 教老婆学Linux运维(一)初识Linux
  4. [转] java开源游戏
  5. 【Kubernetes 系列一】Kubernetes 概述
  6. Spring 2017 Assignments3
  7. c# NPOI 导出23万条记录耗时12秒
  8. 【数学+思维】ZZULIOJ 1531: 小L的区间求和
  9. 使用flash2print 代替 printflash 将office文档 转为flash 在页面中播放
  10. 《Java 8 in Action》Chapter 4:引入流