首页 > 其他分享 >题解:P4563 [JXOI2018] 守卫

题解:P4563 [JXOI2018] 守卫

时间:2024-07-29 11:09:35浏览次数:11  
标签:P4563 保镖 min int 题解 sum JXOI2018 可见 斜率

思路

解法:区间 DP。

本题虽标上紫题,但黄队说了:“不要被颜色所吓倒。”

易得,区间 \([l,r]\) 中最右端的亭子 \(r\) 一定会有保镖。

先说一下可见性判断吧,只要 \(l,r\) 的连线的斜率大于 \(p,r\) 连成的线的斜率大,\(l\) 即是可见的。

如图,红线是 \(r\) 无法看到的,而蓝线是 \(r\) 可以看到的,我们可以从 \(r\) 向 \(l\) 扫描,设 \(p\) 是 \(r\) 可以看到的最左端点,因次 \(p-1\) 必然低于 \(p\)。

则对于 \(l\) 到 \(p-1\) 一段,在 \(p\) 或 \(p-1\) 必有一个保镖。

易得 \(f_{l,r}=sum+\min(f_{l,p-1},f{l,p})\)。

若当前点 \(r\) 可见,则 \(p\) 和 \(p-1\) 中有一个保镖,则 \(sum\) 要加 \(\min(f_{l+1,p-1},f_{l+1,p}\),将 \(p\) 更新成 \(l\)。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5010;
int f[N][N], h[N], n, ans = 0;
bool abledlook(int l, int x, int r) {
	return 1.0 * (h[x] - h[r]) / (x - r) > 1.0 * (h[r] - h[l]) / (r - l);//计算斜率
}
//判断是否可见

signed main() {
	cin >> n;

	for (int i = 1; i <= n; i++)cin >> h[i];
	for (int r = 1; r <= n; r++) {
		ans ^= (f[r][r] = 1);
		int sum = 1, p = 0;
		for (int l = r - 1; l >= 1; l--) {
			if (!p || abledlook(l, p, r))sum += min(f[l + 1][p - 1], f[l + 1][p]), p = l;//更新 p,sum

			ans ^= (f[l][r] = sum + min(f[l][p - 1], f[l][p]));
		}
	}

	cout << ans << "\n";
	return 0;
}

标签:P4563,保镖,min,int,题解,sum,JXOI2018,可见,斜率
From: https://www.cnblogs.com/AUBSwords/p/18329642

相关文章

  • CF1178D Prime Graph 题解
    首先考虑一个问题:如果没有边数是素数的限制,应该怎么构造?这其实很简单,把原图连成一个环即可,每个点度数为\(2\)。接着考虑在原图上加边,注意到\(3\)也是个素数,所以每次可以任意选两个度数为\(2\)的点连边,此时仍然符合条件。这样加边最多可以加\(\left\lfloor\frac{n}{2}\rig......
  • CF685E 题解
    吐槽一下,为啥这道题\(\mathcal{O}(nm)\)可以过。联考的时候做到了这道题,还一直在想更快的算法。。。然后,这联考的数据是自己出的,有\(s=t\)的情况,我反正是完全没有想到,又因为是捆绑测试,直接痛失\(100pts\)。首先考虑转化一下题目。对于一个询问\(l,r,s,t\),就相当于是让你......
  • P4468[SCOI2007]折纸-题解
    题意:有一个左下角为\((0,0)\),右上角为\((100,100)\)的正方形,给你\(n\)个有向线段和\(m\)个询问,将纸片依次按直线折叠,然后每次询问让你求出某个点上有多少层纸。分析:观察到数据范围非常小,于是可以直接对于每个询问\(\mathcal{O}(2^n)\)来求。具体的,对于每一个点,倒着枚......
  • P8540 「Wdoi-2」夜空中的 UFO 恋曲 题解
    hanghangakioi考试的时候在乱猜结论,交了几遍就过了,证明当然是赛后才想的()文中加粗部分是需要读者稍微思考一下原因的地方(不是重点)。先考虑一下样例二,将\(10^{18}\)化成二进制:\(1101...001000000000000000000\)。其实只需要知道末尾有\(18\)个\(0\)就行了,因为在\(x\)......
  • CF1906C Cursed Game 题解
    题目大意交互库有一个\(3\times3\)的01矩阵\(a\),每次询问一个\(n\timesn\)的01矩阵\(b\),交互库会返回一个\((n-2)\times(n-2)\)的01矩阵\(c\),满足:\[c_{x,y}=\bigoplus\limits_{1\lei,j\le3}\left(a_{i,j}\operatorname{AND}b_{x+i-1,y+j-1}\right......
  • 梦熊十三连测第三场题解
    T1本题考察了数论的相关知识。30pts暴力枚举每次洗牌的情况,时间复杂度为\(O(n^2)\)。60pts首先卡牌\(1\)和\(2n\)一直不动,可以不用考虑这两张牌。将位置和剩下的牌上的数字全减\(1\),那么数字为\(k\)的牌操作一次后就会到\(2k\bmod(2n-1)\)的位置。那么问题相当......
  • Maximum Glutton题解
    正常动规,但是赛时死了。分析看到\(n\)很小,但是\(X\)和\(Y\)有点大,所以状态稍微改变一下。设\(dp_{i,j}\)表示已经选到第\(j\)个,且甜度为\(i\)时咸度的最小值。转移方程为:\[dp_{j,k}=\min_{0\lek\lei,a_i\lej\leX}(dp_{j,k},dp_{j-a_i,k-1}+b_i)\]按照\(i,j......
  • CF526G Spiders Evil Plan 题解
    Description给定一棵\(n\)个节点的无根树,每条边有边权。有\(q\)次询问,每次询问给出\(x,y\),你需要选择\(y\)条树上的路径,使这些路径形成一个包含\(x\)的连通块,且连通块中包含的边权和最大。\(n,q\le10^5\),强制在线。Solution考虑只有一组询问怎么快速求答案。容......
  • 【科大讯飞笔试题汇总】2024-07-27-科大讯飞秋招提前批(研发岗)-三语言题解(Cpp/Java/
    ......
  • ABC364 DEF 题解
    ABC364DEF题解D-K-thNearest题目链接赛时想了一个(也许确实是对的)做法,但是代码太难写,一直没写出来……看了官方题解才发现正解其实也很简单……本题最关键的一点是要转换思路:与其考虑“离某个点第\(k\)近的点在哪”,不如考虑“离某个点距离不超过\(x\)的点有多少个”。......