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

P4563 [JXOI2018] 守卫 题解

时间:2024-09-10 17:51:17浏览次数:9  
标签:P4563 保镖 int 题解 JXOI2018 dp

P4563 [JXOI2018] 守卫 题解

不愧是九条可怜的 \(\text{JXOI}\),只能说确实是道好题。

假设当前我们在求 \([l,r]\),我们不难发现 \(r\) 端点一定要放保镖,于是考虑 \(r\) 保镖的最大监视范围 \([x,r]\)。由题意得到对于 \([x,r]\) 中的每个 \(p_1,p_2,\cdots,p_k\),要求斜率 \(t(p_i,r)\le t(p_{i+1},r)\),那么容易得到在 \(p\in[x+1,r-1]\) 处放保镖一定不如在 \(p-1\) 处放置保镖优。

考虑 \(x-1\) 能被谁保护。我们将 \(x-1\) 和 \(r\) 连线 \(l\) 发现 \(x\) 在 \(l\) 以上,\(p\in[x+1,r-1]\) 都在 \(l\) 以下,那么 \(p>x\) 都无法保护 \(x\)。于是 \(x\) 和 \(x-1\) 一定有一个亭子放保镖,记这个亭子为 \(q\),此时我们惊奇地发现这个子问题的答案变为了 \([l,q]\) 的答案,具有最优子结构性质。那么我们正序枚举 \(r\),倒序枚举每个 \(l\),容易写出区间 dp 的式子来。

题目的关键是能发现 \(r\) 端点一定要放保镖的性质并加以利用。

代码:

#include <bits/stdc++.h>
#define N 5005
using namespace std;
int n;
int a[N];
int ans;
int dp[N][N];
double st(int x, int y) {
	return (a[y] - a[x]) * 1.0 / (y - x);
}
int chk(int l, int x, int r) {
	return st(x, r) > st(l, r);
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int r = 1; r <= n; r++) {
		dp[r][r] = 1;
		ans ^= 1;
		int x = 0, sm = 1;
		for (int l = r - 1; l >= 1; l--) {
			if (x == 0 || chk(l, x, r))
				sm += min(dp[l + 1][x - 1], dp[l + 1][x]), x = l;
			dp[l][r] = sm + min(dp[l][x], dp[l][x - 1]);
			ans ^= dp[l][r];
		}
	}			
	cout << ans << "\n";
	return 0;
}

标签:P4563,保镖,int,题解,JXOI2018,dp
From: https://www.cnblogs.com/Rock-N-Roll/p/18406871

相关文章

  • 树上一些点的选 题解
    题意简述给你一棵\(n\)个节点以\(1\)为根的有根树,和一个整数\(m\)。对于树上每一个点\(u\),有三个权值\(X,Y,Z\)。你需要在\(u\)的祖先里(不含\(u\))中选出至少\(X\)个点,记\(S_1\)表示这些点到\(u\)的距离之和;在\(u\)的后代里(不含\(u\))中选出至少\(Y\)个点,......
  • CF717A Festival Organization 题解
    Description一个合法的串定义为:长度在\([l,r]\)之间,且只含0,1,并且不存在连续\(2\)个或更多的\(0\)。现在要选出\(k\)个长度相同的合法的串,问有几种选法,答案模\(10^9+7\)。\(1\leqk\leq200,1\leql\leqr\leq10^{18}\)。Solution容易发现答案为\(\sum_{i=l+2}^{r......
  • 【Py/Java/C++三种语言OD独家2024E卷真题】20天拿下华为OD笔试之【回溯】2024E-字符串
    可上欧弟OJ系统练习华子OD、大厂真题绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)文章目录相关推荐阅读题目描述与示例题目描述输入描述输出描述示例一输入输出说明示例二输入输出说明解题思路代码pythonjavacpp时空复杂度华为OD算法/大厂面......
  • Android中SurfaceView的双缓冲机制和普通View叠加问题解决办法
    本文首发于公众号“AntDream”,欢迎微信搜索“AntDream”或扫描文章底部二维码关注,和我一起每天进步一点点SurfaceView是Android平台上用于高效渲染图形的视图控件。它将内容绘制在一个独立的Surface上,可以直接由渲染线程访问,从而提高性能,尤其是在需要频繁刷新和更新......
  • 题解:CF913C Party Lemonade
    分析因为容量为\(2^{i-1}\),所以对于任意的\(i<j\),第\(j\)种瓶子一定可以通过选择\(2^{j-i}\)个\(i\)种瓶子来实现。定义一个瓶子的性价比为\(\dfrac{\textrm{容量}}{\textrm{价格}}\),即\(\dfrac{2^{i-1}}{c_i}\)。我们可以按照每个瓶子的性价比从高到低排序,依次选择......
  • 题解:CF913D Too Easy Problems
    题意给定一场考试,考试会持续\(T\)毫秒,由\(n\)道题目组成,你可以用\(t_i\)毫秒解决第\(i\)个问题,每个问题给定一个整数\(a_i\)。要求你选出一个试题集合\(S\),若该集合大小为\(k\),它应满足\(T\geq\sum_{i\inS}\limitst_i\),你需要最大化\(\sum_{i\inS}\limits[a_i......
  • 题解:P5618 [SDOI2015] 道路修建
    题意给定一个\(2\timesN\)的网格,网格上的点和上下左右连边。要求支持以下几种操作:修改某条边的边权。求满足\(y\in[l,r]\)的点构成的点集的最小生成树。分析这道题的想法和P4246[SHOI2008]堵塞的交通很相似。注意到\(N,M\leq6\times10^4\),并且查询的是......
  • 题解:P6089 [JSOI2015] 非诚勿扰
    分析首先我们要求出对于第\(i\)位女性,她选择每个列表中的男性的概率是多少。第一轮选择第一位的概率为\(p\),选择第二位的概率为\(p(1-p)\),以此类推。显然第一轮选择第\(k\)位的概率为\(p(1-p)^{k-1}\)。假设列表中有\(n\)名男性,那么第二轮选择第一位的概率为\(p(1-p......
  • 题解:P3968 [TJOI2014] 电源插排
    题意维护一个\(01\)串,初始均为\(0\),支持:单点将\(1\)修改为\(0\)。查询区间中\(1\)的个数。查询最长且最靠右的连续\(0\)段的靠右的中点,并将其改为\(1\)。分析第一个操作和第二个操作显然使用动态开点线段树维护。我们只需要解决第三个操作。我们用平衡树存储......
  • CF1621G Weighted Increasing Subsequences 题解
    题目链接点击打开链接题目解法这种题就感觉每一步都不难想,但串在一起就不会显然考虑位置\(x\)作为\(lis\)的一部分,合法的\(lis\)的个数合法的约束是:令\(lis\)的最后一个位置为\(last\),满足\(\max\{a_{last+1},...,a_n\}>a_x\)不难发现,合法的\(last\)是一段区间......