【DP】【树状数组】方伯伯的玉米田/优美玉米（luogu 3287/金牌导航 数据结构优化DP-5）

本文主要是介绍【DP】【树状数组】方伯伯的玉米田/优美玉米（luogu 3287/金牌导航 数据结构优化DP-5），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

luogu 3287
金牌导航 数据结构优化DP-5

---

题目大意

有n个玉米，给出高度，你可以选择一个区间，使这个区间的玉米高度+1，你可以进行k次这样的操作，查询你操作完后最长不下降子序列最大值

---

代码

对于选择区间[l,r]，如果同时把[r+1,n]也选进去，因为是最长不下降子序列，所以让后面更高满足需求，所以我们把[r+1,n]也选进去，所以每次选择区间都是[i,n]

设$f_{i,j}$为前i个玉米总共选择j次的最长不下降子序列，因为每次选择区间都是[i,n]，所以i被选择了j次，那么有：

$$f_{i,j}=\underset{k<i,c⩽j,a_k+c⩽a_i+j}{\max }(f_{k,c}+1)$$

对于$c⩽j,a_k+c⩽a_i+j$可以建一个二维树状数组维护，每次找满足条件的

---

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define N 10010
using namespace std;
int n, k, a[N], c[510][N];
void add(int x, int y, int z) {for (x++; x <= k + 1; x += x & -x)//因为有0，而树状数组计算不了0，所以要+1for (int jy = y; jy <= 5500; jy += jy & -jy) c[x][jy] = max(c[x][jy], z);return;
}
int ask(int x, int y) {int g = 0;for (x++; x; x -= x & -x)for (int jy = y; jy; jy -= jy & -jy) g = max(g, c[x][jy]);return g;
}
int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i)for (int j = k; j >= 0; --j)add(j, a[i] + j, ask(j, a[i] + j) + 1);printf("%d", ask(k, 5500));return 0;
}

这篇关于【DP】【树状数组】方伯伯的玉米田/优美玉米（luogu 3287/金牌导航 数据结构优化DP-5）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---