标题效果:给定一个序列,能够选择k次每个部分的数量和在范围内+1,寻求操作后LIS最大值
我的做法是不是一个标准的解决方案。
。。5E为什么跑飞的复杂性。
。
。
首先,显而易见的结论是,我们选择k右端点都是n时才干保证最优
知道这个我们就能够DP了- -
令f[i][j]表示前i个数上升j次的最大LIS
那么有f[i][j]=max{f[k][l]|k<i,l<=j,a[k]+l<=a[i]+j}+1
看到三维偏序就能够用二维树状数组了- -
时间复杂度O(nklog(max(ai)+k)logk)
这复杂度跑的飞起真是醉了。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 10100
using namespace std;
int n,k,max_num,ans,a[M];
namespace BIT{
int c[6060][550];
void Update(int x,int y,int val)
{
int i,j;
for(i=x;i<=max_num+k;i+=i&-i)
for(j=y;j<=k+1;j+=j&-j)
c[i][j]=max(c[i][j],val);
}
int Get_Ans(int x,int y)
{
int i,j,re=0;
for(i=x;i;i-=i&-i)
for(j=y;j;j-=j&-j)
re=max(re,c[i][j]);
return re;
}
}
int main()
{
using namespace BIT;
int i,j;
for(cin>>n>>k,i=1;i<=n;i++)
{
scanf("%d",&a[i]);
max_num=max(max_num,a[i]);
}
for(i=1;i<=n;i++)
for(j=k;~j;j--)
{
int temp=Get_Ans(a[i]+j,j+1)+1;
ans=max(ans,temp);
Update(a[i]+j,j+1,temp);
}
cout<<ans<<endl;
return 0;
}
版权声明:本文博客原创文章。博客,未经同意,不得转载。