题解+代码详细解释
2023-10-20 19:15:38
发布于:江苏
这段代码解决了一个问题,其中有两位小牛Ella和Bella,它们要从农场的一个大正方形草地的左下角到右上角,使用一个很长的且很锋利的线,割掉所有线覆盖的草。但是,它们必须经过一些特定的花朵,这些花朵是草地上的点,它们的位置已知。问题的目标是选择尽可能多的花朵,同时割掉尽可能少的草。
下面是代码的详细解释:
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define M 1000000
#define LL long long
#define INF (LL)1e18
using namespace std;
这部分是代码的头部,包括了一些宏定义、头文件和命名空间的声明。
int n, m; // 输入的花朵数量和草地大小
struct P { int x, y; }; // 代表一个点的结构体
vector<P> w[N + 5]; // 存储花朵的坐标
vector<LL> f[N + 5]; // 存储动态规划的中间结果
在这里,定义了一些全局变量和数据结构。n 表示花朵的数量,m 表示草地的大小。struct P 表示一个点的坐标,它包括 x 和 y 坐标。vector<P> w[N + 5] 存储花朵的坐标,vector<LL> f[N + 5] 存储动态规划的中间结果。
namespace FastIO
{
// 读取输入的快速IO函数
// ...
} using namespace FastIO;
namespace DP
{
// 动态规划的命名空间
// ...
}
这部分定义了两个命名空间,用于快速IO和动态规划。
class SegmentTree
{
private:
// 私有成员和方法
// ...
public:
// 公有方法
// ...
}
定义了一个名为 SegmentTree 的类,用于构建线段树,其中包含了一些私有成员和方法,用于管理线段树的操作。
struct TreeArray
{
// 树状数组的结构
int a[M + 5];
I void U(RI x, CI v) { // 更新操作
W (x <= m && a[x] < v)
a[x] = v, x += x & -x;
}
I int Q(RI x) { // 查询操作
RI t = 0;
W (x)
t = max(t, a[x]), x -= x & -x;
return t;
}
}
I int FX(Con vector<P>& v, CI x) { // 二分查找横坐标小于x的位置
RI l = 0, r = v.size() - 1, mid;
W (l ^ r)
v[mid = l + r + 1 >> 1].x < x ? l = mid : r = mid - 1;
return l;
}
I int FY(Con vector<P>& v, CI y) { // 二分查找纵坐标小于y的位置
RI l = 0, r = v.size() - 1, mid;
W (l ^ r)
v[mid = l + r - 1 >> 1].y < y ? r = mid : l = mid + 1;
return r;
}
这部分定义了一个名为 TreeArray 的结构,用于实现树状数组的操作。还有两个辅助函数 FX 和 FY,用于二分查找花朵坐标。
int main()
{
// 主函数
// ...
}
这是主函数入口,用于解决问题。接下来是主要的代码逻辑。
RI i, j, x;
for (read(n), read(m), i = 1; i <= n; ++i)
read(p[i].x), read(p[i].y);
RI Mx = 0;
for (sort(p + 1, p + n + 1), i = 1; i <= n; ++i) {
T.U(p[i].y, x = T.Q(p[i].y) + 1);
w[x].push_back(p[i]);
Mx = max(Mx, x);
}
在这部分,首先读取输入的花朵数量和草地大小。然后对花朵按照横坐标进行排序,同时使用树状数组来计算每个花朵在其横坐标上的LIS(最长上升子序列),并将花朵按照LIS分层存储在 w 数组中。
for (w[0].push_back((P){0, 0}), f[0].push_back(0), i = 1; i <= Mx; S.Solve(i++)) {
for (sz = w[i - 1].size(), x = w[i].size(), j = 0; j ^ x; ++j)
S.K(FY(w[i - 1], w[i][j].y), FX(w[i - 1], w[i][j].x), j);
f[i].push_back(INF);
}
在这部分,初始化 w[0] 和 f[0],然后进行循环,每次处理一层的花朵。对于每层的花朵,使用 S.K 方法来计算当前花朵可以影响到的范围,并将结果存储在 f 数组中。
LL t = INF;
for (j = 0; j ^ x; ++j)
t = min(t, f[Mx][j] + 1LL * (m - w[Mx][j].x) * (m - w[Mx][j].y));
return printf("%lld\n", t), 0;
最后,在这部分,计算最终答案。遍历最后一层的花朵,选择一条路径,使得割掉的草最少,同时经过尽可能多的花朵,然后输出最小可能的割草量。
这段代码使用了动态规划和线段树来解决一个优化问题,其中需要最大化经过的花朵数量,同时最小化割草量。
这里空空如也
有帮助,赞一个