正题
金牌导航 数据结构优化DP-1
题目大意
平面上有n个点，让你选择若干点，连接x坐标相邻的点，其中连续上升或下降的为一段，问你有多少中选择方案，使得段数为k
解题思路
设fi,j,0/1f_{i,j,0/1}fi,j,0/1为到第i个点，已经有j段，且第j段下降/上升的方案数
那么分类讨论：
1.先上升后下降
2.连续下降
3.先下降后上升
4.连续上升
对于找满足的转移点，可以建树状数组解决
代码
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define N 100010#define wyc 100007using namespace std;int n, m, x, a[N], g[N];struct Tree{int num, c[N];void add(int x, int y){num = (num + y) % wyc;for (; x <= 100000; x += x&-x)c[x] = (c[x] + y) % wyc;return;}int ask(int x){int sum = 0;for (; x; x -= x&-x)sum = (c[x] + sum) % wyc;return sum; }int askk(int x){return (num + wyc - ask(x)) % wyc;}}T[11][2];bool cmp(int x, int y){return g[x] < g[y];}int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){scanf("%d%d", &x, &a[i]);g[a[i]] = x;}sort(a + 1, a + 1 + n, cmp);for (int i = 1; i <= n; ++i){T[0][0].add(a[i], 1);//没有连边的点T[0][1].add(a[i], 1);for (int j = 1; j <= m; ++j){T[j][1].add(a[i], (T[j][1].ask(a[i] - 1) + T[j - 1][0].ask(a[i] - 1)) % wyc);//先上升和先下降T[j][0].add(a[i], (T[j][0].askk(a[i]) + T[j - 1][1].askk(a[i])) % wyc);}}printf("%d", (T[m][0].ask(100000) + T[m][1].ask(100000)) % wyc);return 0;}
