[JXOI2018]守卫
2024-10-13 23:13:54
嘟嘟嘟
正如某题解所说,这题很有误导性:我就一直在想凸包。
随便一个数据,就能把凸包hack掉:
这样我们的点G就gg了。
所以正解是什么呢?dp。
题解看这位老哥的吧,我感觉挺好懂的:题解 P4563 【[JXOI2018]守卫】
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e3 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
struct Point
{
ll x, y;
In Point operator + (const Point& oth)const
{
return (Point){x + oth.x, y + oth.y};
}
In Point operator - (const Point& oth)const
{
return (Point){x - oth.x, y - oth.y};
}
In ll operator * (const Point& oth)const
{
return x * oth.y - y * oth.x;
}
}p[maxn];
int dp[maxn][maxn];
int main()
{
n = read();
for(int i = 1; i <= n; ++i) p[i].x = i, p[i].y = read();
int ans = 0;
for(int i = 1; i <= n; ++i)
{
dp[i][i] = 1; ans ^= 1;
int sum = 1, pos = 0;
for(int j = i - 1; j; --j)
{
if(!pos || (p[pos] - p[i]) * (p[j] - p[i]) < 0)
sum += min(dp[j + 1][pos - 1], dp[j + 1][pos]), pos = j;
dp[j][i] = sum + min(dp[j][pos - 1], dp[j][pos]);
ans ^= dp[j][i];
}
}
write(ans), enter;
return 0;
}
最新文章
- 自定义一个可复用的BaseAdapter
- PHP递归重新排序无限级分类数组
- Java学习笔记(八)&mdash;&mdash;封装
- CentOS升级MySQL到5.5
- Poj 1061 青蛙的约会(扩展GCD)
- noi2006day2_最大获利 网络流
- C# 模式窗口下更新进度条
- 新闻类App使用的组件
- [Java 8 Lambda] java.util.stream 简单介绍
- CodeForces--TechnoCup--2016.10.15--ProblemB--Bill Total Value(字符串处理)
- 一条sql执行过长的时间,你如何优化,从哪些方面?
- learning makefile 模式规则
- OO第二单元(电梯)单元总结
- springcloud学习笔记
- webpack项目打包配置
- HDU-6033 Add More Zero
- 移动app传统测试流程优化
- IIS时间格式设置
- Eclipse更改皮肤
- (Lua) C++ 呼叫 Lua 的變數、函式
热门文章
- Java IO(2)阻塞式输入输出(BIO)
- Golang &#27491;&#21017;&#34920;&#36798;&#24335;Regex&#30456;&#20851;&#36164;&#26009;&#25972;&#29702;
- Docker 系列五(Docker Compose 项目).
- 现在有两个变量,分别是a = 3, b = 4,那么我们不用第三个变量来调换a和b的值。
- JavaScript 变量及类型
- 2018-01-02 JavaScript实现ZLOGO: 用语法树实现多层循环
- Ambari架构源码解析
- AI从业者需要应用的10种深度学习方法
- Android Room框架学习笔记
- ORA-12514, TNS:listener does not currently know of service requested in connect descriptor案例2