正題

金牌導航 數據結構優化DP-1

---

題目大意

平面上有n個點，讓你選擇若干點，連接x坐標相鄰的點，其中連續上升或下降的為一段，問你有多少中選擇方案，使得段數為k

---

解題思路

設$f_{i,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 100007 using 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; }

總結

以上是生活随笔為你收集整理的【DP】【树状数组】折线统计（金牌导航 数据结构优化DP-1）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。