AcWing 3662. 最大上升子序列和
原题链接
困难
作者:
代码改变头发
,
2021-06-14 16:39:06
,
所有人可见
,
阅读 567
dp + 树状数组优化&离散化
算法思路
DP
dp[i] = a[i] (合法的j可能不存在)
dp[i] = max( dp[j] + a[i] ) (0<=j<i && a[j] < a[i]);
优化
max( dp[j] )
用树状数组tr[x]:数值<=x的最大dp值(结尾值<=x的上升子序列最大和)
离散化
a[i]取到1e9而n取1e5,需要用到离散化
离散化:把所有数值从小到达排序,以其排序后的下标作为索引
时间复杂度
O(nlogn)
C++ 代码
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
int a[N];
ll dp[N];
ll tr[N];
vector<int> alls; //用来离散化
int find(int x)
{//a[i]在alls中的下标 从1开始
return lower_bound(alls.begin(),all.end(),x) - alls.begin() + 1;
}
int lowbit(int x)
{
return x & -x;
}
void add(int x, ll v)
{
for( int i = x; i <= n; i += lowbit(i) ) tr[i] = max( tr[i], v );
}
ll query(int x)
{
ll res = 0;
for( int i = x; i; i -= lowbit(i) ) res = max( res, tr[i] );
return res;
}
int main()
{
scanf("%d",&n);
for( int i = 0; i < n; i++ )
{
scanf("%d",&a[i]);
alls.push_back(a[i]);
}
//离散化
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//dp过程
ll res = 0;
for( int i = 0; i < n; i++ )
{
int k = find(a[i]);
dp[i] = query(k-1) + a[i];
res = max( res, dp[i] );
add(k,dp[i]);
}
printf("%lld\n",res);
return 0;
}