题面
题面下载
算法
转化题意
说白了就是给了你一堆点，让你数这种折线有多少个 (严格向下走，并且横坐标之间的差越来越小)
看着像一种在 y 轴方向排序的 dp
但是由于是折线, 所以需要加一维来判断转向
dp 设计
状态设计
\(dp_{i, 0/1}\) 表示第 i 个点, 是向左下还是右上
状态转移方程
最初想到从 y 轴, 从上往下递推, 但是这样满足不了抽象的 x 轴约束, 因此考虑从 x 轴方向递推
于是有递推式子
\[dp_{i, 0} = dp_{i, 0} + dp_{j, 1} ( y_j < y_i )
\]
\[dp_{j, 1} = dp_{i, 0} + dp_{j, 1} ( y_j > y_i )
\]
边界条件
\[dp_{i, 0} = 1, dp_{i, 1} = 1
\]
时间复杂度
优秀啊
代码
#include <bits/stdc++.h>
const int MAXN = 1e5 + 20;
const int MOD = 1e9 + 7;
int n, m;int dp[MAXN][2];int ans = 0;
struct node
{int x, y;friend bool operator < (node a, node b){return a.x < b.x;}
} p[MAXN];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d %d", &p[i].x, &p[i].y);}std::sort(p + 1, p + n + 1);for (int i = 1; i <= n; i++){dp[i][0] = dp[i][1] = 1;for (int j = i - 1; j >= 1; j--){if (p[i].y > p[j].y){dp[i][0] = (dp[i][0] + dp[j][1]) % MOD;}else{dp[j][1] = (dp[i][0] + dp[j][1]) % MOD;}}}for (int i = 1; i <= n; i++){ans = (ans + (dp[i][0] + dp[i][1] - 1) % MOD) % MOD;}printf("%d\n", ans);return 0;
}总结
这说明了有些看似顺序很尴尬的题目，说不定瞎搞搞就能减少一个数量级的复杂度
