蒟蒻刚学DP和树状数组,跟着题解敲的,求助QAQ
查看原帖
蒟蒻刚学DP和树状数组,跟着题解敲的,求助QAQ
221002
hytree楼主2020/10/23 15:04

RT

#include<bits/stdc++.h>
using namespace std;
#define re register
int n,ans,maxh,k,f[6010][601],a[10010];
void change(int x,int y,int c)
{
	for(;x<=maxh+k;x+=(x&(-x)))
	for(;y<=k+1;y+=(y&(-y)))
	f[x][y]=max(f[x][y],c);
}
int ask(int x,int y)
{
	re int res=0;
	for(;x;x-=(x&(-x)))
	for(;y;y-=(y&(-y)))
	res=max(res,f[x][y]);
	return res;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(re int i=1;i<=n;++i)
	scanf("%d",a+i),maxh=max(maxh,a[i]);
	for(re int i=1;i<=n;++i)
	for(re int j=k;j>=0;--j)
	{
		re int x=ask(a[i]+j,j+1)+1;
		ans=max(ans,x);change(a[i]+j,j+1,x);
	}
	cout<<ans;
	return 0;
}

实在不知道错在哪了,怎么办,求助QWQ

2020/10/23 15:04
加载中...