题目大意：小 Y 十分喜爱光学相关的问题,
一天他正在研究折射.他在平面上放置了 n 个折射装置,
希望利用这些装置画出美丽的折线.折线将从某个装置出发,
并且在经过一处装置时可以转向, 若经过的装置坐标依次为 (x1, y1),(x2, y2),
. . .(xk, yk), 则必须满足:
\[• ∀j ∈ (1, k], y_j < y_j−1\]
\[• ∀j ∈ (2, k], x_{j−2} < x_j <
x{j−1}\;or\;x{j−1} < x_j < x_{j−2}\]
现在他希望你能告诉他, 一共有多少种不同的光线能被他画出来,
两种光线不同当且仅当经过的折射装置的集合不同. 你只需要告诉他答案对109 +
7 取模后的结果.（其中n属于6000）
自己的错误思路：
看到数据范围，猜是dp或者模拟
于是开始构思思路：显然按y坐标从大到小排序之后，每一个点，都可以从他后面的点转移过来
但是转移的时候防止出现以下情况：（别管连边，只是折线的方向）
显然，我们1这个节点可以从4号点转移答案过来（先别管怎么转移的）
同理，我们也可以从2号点转移过来，但是如果从2号点转移的话，就不满足：
\[• ∀j ∈ (2, k], x_{j−2} < x_j <
x{j−1}\;or\;x{j−1} < x_j < x_{j−2}\]
满足上述条件的，显然只有以下两种情况：
对于类似于上图“1-2-3”这样的折线，我们设一个\(right[x]\)表示以x作为居右侧的转折点，所能得到的折线方案数目
对于类似于上图“4-5-6”这样的折线，我们设一个\(left[x]\)表示以x作为居右侧的转折点，所能得到的折线方案数目
然后就可以倒着往前推了
特别的，我们发现如果一个点在另一个点的下面，那么他一定会有贡献，无论大小
假设我们当前枚举到的为\(t\)，我们起初可以由\(t\)向任意方向指出一条射线
若在\(t\)横坐标的左边有一个点\(g\)，显然，可以连一条由\(t\)指向\(g\)的边（不继续延伸），在继续扩展，我们以\(g\)为居右侧的转折点，累加他的贡献，并累加到以\(t\)为居左侧的转折点的计数数组里面
再\(t\)横坐标的右边亦是同理，详见代码
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 66, mod = 1e9 + 7;
int n, ans;
int l[N], r[N], res[N];
struct yhzhyhm
{
int x, y;
bool operator < (const yhzhyhm &yhzh) const {return y > yhzh.y;}
}yh[N];
signed main()
{
int i, j;
n = read();
for (i = 1; i <= n; ++ i) yh[i].x = read(), yh[i].y = read();
sort(yh + 1, yh + 1 + n);
l[n] = r[n] = 0, res[n] = 1;
for (i = n - 1; i >= 1; -- i)
{
int num(0), num1(0), num2(0);
res[i] = 1;
for (j = i + 1; j <= n; ++ j)
{
if (yh[i].x > yh[j].x)
{
num1 = (num1 + 1) % mod;
res[i] = (res[i] + l[j] % mod) % mod, r[i] = (r[i] + l[j]) % mod;
}
if (yh[i].x < yh[j].x)
{
num2 = (num2 + 1) % mod;
res[i] = (res[i] + r[j] % mod) % mod, l[i] = (l[i] + r[j]) % mod;
}
num = (num + 1) % mod;
}
res[i] = (res[i] + num) % mod;
r[i] = (r[i] + num1 % mod) % mod;
l[i] = (l[i] + num2 % mod) % mod;
}
for (i = 1; i <= n; ++ i) ans = (ans + res[i] % mod) % mod;
put(ans);
return 0;
}
|
正解：
其实暴力的做法是\(O(n^3)\)，但是我们可以xjb优化一下就成为n方
显然的道理：按照y排序搞搞搞不能进行优化，所以我们按照x从小到大排序
状态：\(f[i][0]\)表示以i为起点向左下拐的方案数目，设\(f[i][1]\)表示以i为起点向右下拐的数目
初始化：\(f[i][0]=f[i][1]=1\)
对于当前枚举到的i，我们考虑i之前的某一个节点j
如果发现\(y_j>y_i\)显然i是j的转折点，所以\(f[j][1]+=f[i][0]\)
如果发现\(y_j<y_i\)显然j是i的转折点，所以\(f[i][0]+=f[j][1]\)
一个小细节：最后的ans加成的时候，显然需要\(f[i][0]+f[i][1]-1\)（想一想，为什么？）
因为我们初始化的时候，都初始化为1，但实际上是有一条重复的，就是我们假如从这个点出发，谁也不连，直接就是一条折线
但是我们那两个状态把这个算重复了所以需要减去1
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 66, mod = 1e9 + 7;
struct yhzhyhm
{
int x, y;
bool operator < (const yhzhyhm &yhzh) const {return x < yhzh.x;}
}yh[N];
int n, res, f[N][6];
signed main()
{
int i, j;
n = read();
for (i = 1; i <= n; ++ i) yh[i].x = read(), yh[i].y = read();
sort(yh + 1, yh + 1 + n);
for (i = 1; i <= n; ++ i)
{
f[i][0] = f[i][1] = 1;
for (j = i - 1; j >= 1; -- j)
{
if (yh[i].y > yh[j].y) f[i][0] = (f[i][0] + f[j][1]) % mod;
else f[j][1] = (f[j][1] + f[i][0]) % mod;
}
}
for (i = 1; i <= n; ++ i) res = (res + (f[i][0] + f[i][1] - 1) % mod) % mod;
put(res);
return 0;
}
|