CodeForces 1083 E The Fair Nut and Rectangles 斜率优化DP
2024-09-01 07:44:31
题意:有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 ;
}
最新文章
- Android Studio Lambda Config
- HDU1502/Luogu1352/UVa1220 party[树形DP]
- VTK初学一,b_PolyVertex多个图形点的绘制
- OAF与Windows 7版本不兼容黑屏卡顿问题
- mongodb地理位置索引
- C# #define
- ImageMagick提取图像原始数据(ImageData/RawData)
- ArcEngine 添加字段
- bzoj1632 [Usaco2007 Feb]Lilypad Pond
- 解决linux top命令提示的unknown terminal type的问题
- margin重叠
- 【京东账户】——Mysql/PHP/Ajax爬坑之页头页尾加载
- Scrapy1.4爬取笑话网站数据,Python3.5+Django2.0构建笑话应用
- regression and anova
- 【SVN】关于钩子的一些使用
- hive数据导出到本地目录 抛异常
- (后端)Java中关于金额大小写的工具类
- 查看Java JVM参数配置信息命令
- Python中 __init__的通俗解释?附修饰器contextmanager的理解
- Java – How to get current date time
热门文章
- 准时制生产(Just in Time,JIT)
- Usaco Training [2.1] The Castle 搜索
- 教老婆学Linux运维(一)初识Linux
- [转] java开源游戏
- 【Kubernetes 系列一】Kubernetes 概述
- Spring 2017 Assignments3
- c# NPOI 导出23万条记录耗时12秒
- 【数学+思维】ZZULIOJ 1531: 小L的区间求和
- 使用flash2print 代替 printflash 将office文档 转为flash 在页面中播放
- 《Java 8 in Action》Chapter 4:引入流