正题

题目链接:https://www.luogu.com.cn/problem/P3287

---

题目大意

$n$个玉米高度不同，可以选择$k$个区间拔高$1$个高度，求最长不降子序列长度。

---

解题思路

显然每次拔高都是拔一个后缀，所以我们设$f_{i,j}$表示到第$i$个玉米，拔到现在包含了$j$个拔高的后缀时的最大答案。
$$f_{i,j}=max\{f_{h,k}\}(a_i+j\ge a_h+k,j\ge k)$$

用二维树状数组维护一下即可

时间复杂度$O(nk\log (a_i+k)\log k)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=11000; int n,k,a[N],t[510][5600],f[N][510]; void Change(int x,int y,int val){for(int i=x;i<=k;i+=lowbit(i))for(int j=y;j<=5500;j+=lowbit(j))t[i][j]=max(val,t[i][j]);return; } int Ask(int x,int y){int ans=0;for(int i=x;i;i-=lowbit(i))for(int j=y;j;j-=lowbit(j))ans=max(ans,t[i][j]);return ans; } int main() {scanf("%d%d",&n,&k);int ans=0;k++;for(int i=1;i<=n;i++){scanf("%d",&a[i]); for(int j=k;j>=1;j--){f[i][j]=Ask(j,a[i]+j)+1;Change(j,a[i]+j,f[i][j]);ans=max(ans,f[i][j]);}}printf("%d",ans); }

总结

以上是生活随笔为你收集整理的P3287-[SCOI2014]方伯伯的玉米田【二维树状数组,dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。