题目链接
郑州轻工业大学西风校区的招新赛B题。其他题目都比较水就不写了。这个题用了线段树优化,但是不用也行(写都写了,就用了)。
题目描述有问题,“如果两相邻元素 b i , b i + 1 b_i, b_{i+1} bi,bi+1 满足 b i > b i + 1 b_i > b_{i+1} bi>bi+1,则惩罚值 + t +t +t ”有误。应该是 “如果两相邻元素 b i , b i + 1 b_i, b_{i+1} bi,bi+1 满足 b i ≥ b i + 1 b_i \ge b_{i+1} bi≥bi+1,则惩罚值 + t +t +t ”。给出题人发邮件了不过目前还没修。
3151: 江莉数组
思路:
感觉和这场的C题的dp有点像。不过真写起来差的还是挺多的。
先不管江莉值,剩下部分的dp还是比较明显的:设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个数,以值 j j j 结尾的最大价值。转移方程也比较明显: d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ − 200 ∼ i − 1 ] + a i , d p [ i − 1 ] [ i ∼ 200 ] − t + a i } dp[i][j]=max\{dp[i-1][j],dp[i-1][-200\sim i-1]+a_i,\\dp[i-1][i\sim 200]-t+a_i\} dp[i][j]=max{dp[i−1][j],dp[i−1][−200∼i−1]+ai,dp[i−1][i∼200]−t+ai}发现我们第 i i i 个位置上的 d p dp dp 值只和第 i − 1 i-1 i−1 个位置的 d p dp dp 值有关,所以我们直接优化掉第一维,这样状态转移就变成了 d p [ j ] = m a x { d p [ j ] , d p [ − 200 ∼ i − 1 ] + a i , d p [ i ∼ 200 ] − t + a i } dp[j]=max\{dp[j],dp[-200\sim i-1]+a_i,dp[i\sim 200]-t+a_i\} dp[j]=max{dp[j],dp[−200∼i−1]+ai,dp[i∼200]−t+ai}这时时间复杂度为 O ( 400 n ) O(400n) O(400n),时间已经达标了,但是我们仍然可以优化,用线段树维护区间最大值,这样查询 m a x { d p [ − 200 ∼ i − 1 ] } max\{dp[-200\sim i-1]\} max{dp[−200∼i−1]} 以及 m a x { d p [ i ∼ 200 ] } max\{dp[i\sim 200]\} max{dp[i∼200]} 时就会变成 l o g log log 级别,整个时间复杂度就变成了 O ( l o g ( 400 ) n ) O(log(400)n) O(log(400)n) 了。
现在加入江莉值,其实不难发现,中间的项相消了,整个江莉值其实就是右端点减去左端点 r − l r-l r−l。我们减左端点好说,我们在 d p dp dp 值选取第一个数的时候额外减去下标即可。右端点有点难办,因为我们不知道它什么时候会停。我们可以用上面那道题的做法,额外弄个 d p 2 dp2 dp2。
不过这个题有个性质,那就是以某个值结尾时,这个值一定是最后一个,否则一定不优。因此我们知道了 d p [ j ] dp[j] dp[j],我们其实就已经知道它的右端点位置在哪了,就在最后一个 j j j 出现的位置。
code:
因为 a i a_i ai 的值有可能是负数,所以要加偏移量,都变成正数来处理。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int offs=205;
const ll linf=1e18;int n,t;
ll a[maxn],ans;struct segement_tree{#define ls p<<1#define rs p<<1|1int n=offs<<1;struct Node{ll mx;Node(ll mx=-linf):mx(mx){};}tr[offs<<5];void push_up(int p){tr[p].mx=max(tr[ls].mx,tr[rs].mx);}void modify(int p,int l,int r,int id,ll x){if(l==r){tr[p].mx=x;return;}int mid=(l+r)>>1;if(id<=mid)modify(ls,l,mid,id,x);else modify(rs,mid+1,r,id,x);push_up(p);}void mdy(int id,ll x){modify(1,1,n,id,x);}ll query(int p,int l,int r,int L,int R){if(L<=l && r<=R){return tr[p].mx;}int mid=(l+r)>>1;if(mid>=R)return query(ls,l,mid,L,R);else if(mid<L)return query(rs,mid+1,r,L,R);else return max(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));}ll qmx(int l,int r){return query(1,1,n,l,r);}ll q(int idx){return qmx(idx,idx);}#undef ls#undef rs}tr;int main(){cin>>n>>t;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){ll v=max(a[i]-i,max(tr.qmx(1,a[i]+offs-1)+a[i],tr.qmx(a[i]+offs,offs<<1)+a[i]-t));tr.mdy(a[i]+offs,max(tr.q(a[i]+offs),v));ans=max(ans,v+i);}cout<<ans;return 0;
}