线性dp+树状数组优化
先来看朴素版的做法:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll dp[N];
int a[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
dp[1]=a[1];
for(int i=2;i<=n;i++){
for(int j=i-1;j;j--){
if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+a[i]);
}
}
ll res=0;
for(int i=1;i<=n;i++)res=max(res,dp[i]);
printf("%d",res);
return 0;
}
dp[i]表示以a[i]结尾的子序列中和最大的子序列,求dp[i]时需要寻找前面已经出现过的,结尾小于a[i]的所有子序列中子序和最大的那个,并且把a[i]加到该子序列后面去,这种做法的复杂度在O(n^2)级别。
上述操作可以转换为如下需求:
1.在某个范围内(不大于a[i])查找最大的数。
2.插入一个新的数(新增一个dp[i]),并且维护这个范围内的最值
我们可以使用树状数组来维护某个区间的最值,并且以O(logn)的时间去查询这个区间内的最值。
注意到所有的数据数量只有10^5,但是数据范围有10^9,因此考虑使用离散化,loc(a[i])表示离散化后的位置,find(loc(a[i]))表示查询在小于a[i]的所有dp中的最大值。
代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll dp[N],tr[N];
int a[N],b[N];
int n;
int lowbit(int x){
return x&-x;
}
void add(int x,ll value){
for(int i=x;i<=n;i+=lowbit(i))tr[i]=max(tr[i],value);
}
ll find(int x){
ll res=0;
for(int i=x;i;i-=lowbit(i))res=max(res,tr[i]);
return res;
}
int loc(int x){//离散化
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(b[mid]>x)r=mid;
else if(b[mid]==x)return mid;
else l=mid+1;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)b[i]=a[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
int t=loc(a[i])-1;
dp[i]=find(t)+a[i];
add(t+1,dp[i]);
}
ll res=0;
for(int i=1;i<=n;i++)res=max(res,dp[i]);
printf("%lld",res);
return 0;
}