正題

題目鏈接:https://www.luogu.com.cn/problem/P3287

---

題目大意

$n$個(gè)玉米高度不同，可以選擇$k$個(gè)區(qū)間拔高$1$個(gè)高度，求最長(zhǎng)不降子序列長(zhǎng)度。

---

解題思路

顯然每次拔高都是拔一個(gè)后綴，所以我們?cè)O(shè)$f_{i,j}$表示到第$i$個(gè)玉米，拔到現(xiàn)在包含了$j$個(gè)拔高的后綴時(shí)的最大答案。
$$f_{i,j}=max\{f_{h,k}\}(a_i+j\ge a_h+k,j\ge k)$$

用二維樹狀數(shù)組維護(hù)一下即可

時(shí)間復(fù)雜度$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); }

總結(jié)

以上是生活随笔為你收集整理的P3287-[SCOI2014]方伯伯的玉米田【二维树状数组,dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。