UVaLive 7374 Racing Gems (DP,LIS)
DP UVALive LIS
2023-09-11 14:17:18 时间
题意:以辆赛车可以从x轴上任意点出发,他的水平速度允许他向每向上移动v个单位,就能向左或向右移动v/r个单位(也就是它的辐射范围是个等腰三角形)
现在赛车从x轴出发,问它在到达终点前能吃到的最多钻石。
析:那个v是怎么变那个是不变的。比例考虑每个钻石的向下辐射范围,并且将其投影到x轴上的两个点,(辐射范围与x轴的两个焦点),然后我们就把题目转化成了一个区间覆盖问题,
我们可以在每一个钻石求出一个覆盖范围,什么意思呢,既然水平速度 向左的最大值等于向右的最大值,那么肯定是一个等腰三角形了,只需要求出所有钻石在X轴上所有覆盖范围,求出
有多少个完全覆盖的钻石就是答案!
我们用x<y表示x区间被y区间覆盖,即求二维最长的上升子序列:a1<=a2<=...<=an。
我们按每个钻石的左端点排序,然后跑右端点的最长不下降子序列就可以了。由于数据比较大,用二分处理成nlogn的复杂度。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <functional> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <deque> #include <map> #include <cctype> #include <stack> #include <sstream> #include <cstdlib> using namespace std ; #include <ctime> typedef long long LL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL LNF = 0x3f3f3f3f3f; const double inf = 0x3f3f3f3f3f3f; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; const char *mark = "+-*"; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; int n, m; inline int Min(int a, int b){ return a < b ? a : b; } inline int Max(int a, int b){ return a > b ? a : b; } inline LL Min(LL a, LL b){ return a < b ? a : b; } inline LL Max(LL a, LL b){ return a > b ? a : b; } struct node{ LL x, y; bool operator < (const node &p)const{ return x > p.x || (x == p.x && y < p.y); } }; node a[maxn]; LL dp[maxn]; int DP(){ fill(dp, dp+n, LNF); for(int i = 0; i < n; ++i) *upper_bound(dp, dp+n, a[i].y) = a[i].y; return lower_bound(dp, dp+n, LNF) - dp; } int main(){ int r, h, w; while(scanf("%d %d %d %d", &n, &r, &w, &h) == 4){ for(int i = 0; i < n; ++i){ LL x, y; scanf("%lld %lld", &x, &y); a[i].x = r * x - y; a[i].y = r * x + y; } sort(a, a+n); int ans = DP(); printf("%d\n", ans); } return 0; }
相关文章
- 【Android】dip、dp、sp、pt和px的区别
- hdu 1087 最长上升序列和 dp
- POJ 2955 Brackets 区间DP
- Bomb(要49)--数位dp
- poj3342Party at Hali-Bula(树形dp)
- Java实现 蓝桥杯 算法提高VIP 摆花 dp 记忆搜索 2种做法 多重背包
- HDU 1300 Pearls (DP)
- 数字三角形(线性DP)
- Leetcode2038. 如果相邻两个颜色均相同则删除当前颜色(medium, dp, greedy)
- DL之CNN:卷积神经网络算法应用之卷积神经网络实践技巧(DA/DP/WI/BN/H/O/R)、优化技术经验之详细攻略
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习2
- poj 3635 Full Tank? ( 图上dp )
- Codeforces 41D Pawn 简单dp
- 博弈型动态规划模板——精髓:把两个选手当成一个人,每次面对a[i…j]选最优解,用dfs+cache做最直观,再考虑修改为dp数组
- 377. Combination Sum IV——DP本质:针对结果的迭代,dp[ans] <= dp[ans-i] & dp[i] 找三者关系 思考问题的维度+1,除了数据集迭代还有考虑结果
- 1015. 摘花生(线性DP)
- 动态规划——最长公共子序列(闫氏DP)