专业模板网站制作服务,国内十大网站建设公司,俄罗斯局势最新消息,长春专业做网站公司排名正题
题目链接:https://www.luogu.com.cn/problem/P3287 题目大意 nnn个玉米高度不同#xff0c;可以选择kkk个区间拔高111个高度#xff0c;求最长不降子序列长度。 解题思路
显然每次拔高都是拔一个后缀#xff0c;所以我们设fi,jf_{i,j}fi,j表示到第iii个玉米#x…正题
题目链接:https://www.luogu.com.cn/problem/P3287 题目大意
nnn个玉米高度不同可以选择kkk个区间拔高111个高度求最长不降子序列长度。 解题思路
显然每次拔高都是拔一个后缀所以我们设fi,jf_{i,j}fi,j表示到第iii个玉米拔到现在包含了jjj个拔高的后缀时的最大答案。 fi,jmax{fh,k}(aij≥ahk,j≥k)f_{i,j}max\{f_{h,k}\}(a_ij\geq a_hk,j\geq k)fi,jmax{fh,k}(aij≥ahk,j≥k)
用二维树状数组维护一下即可
时间复杂度O(nklog(aik)logk)O(\ nk\log(a_ik)\log k\ )O( nklog(aik)logk ) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N11000;
int n,k,a[N],t[510][5600],f[N][510];
void Change(int x,int y,int val){for(int ix;ik;ilowbit(i))for(int jy;j5500;jlowbit(j))t[i][j]max(val,t[i][j]);return;
}
int Ask(int x,int y){int ans0;for(int ix;i;i-lowbit(i))for(int jy;j;j-lowbit(j))ansmax(ans,t[i][j]);return ans;
}
int main()
{scanf(%d%d,n,k);int ans0;k;for(int i1;in;i){scanf(%d,a[i]); for(int jk;j1;j--){f[i][j]Ask(j,a[i]j)1;Change(j,a[i]j,f[i][j]);ansmax(ans,f[i][j]);}}printf(%d,ans);
}
