线段树优化,双倍经验的过了,这题70
  • 板块P2034 选择数字
  • 楼主lc_lca
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/6/3 15:12
  • 上次更新2023/11/7 01:14:33
查看原帖
线段树优化,双倍经验的过了,这题70
120340
lc_lca楼主2020/6/3 15:12
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100010;
int a[maxn],n;
int max(int a,int b)
{
	if(a>b) return a;
	return b;
}
struct segment_tree{
	int l,r,dat;
}t[maxn<<2];
void build(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	if(l==r)
	{
		t[p].dat=-(0x3f3f3f3f3f3f);
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void change(int p,int x,int z)
{
	if(t[p].l==t[p].r)
	{
		t[p].dat=z;
		return; 
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) change(p<<1,x,z);
	else change(p<<1|1,x,z);
	t[p].dat=max(t[p<<1].dat,t[p<<1|1].dat);
}
int query(int p,int x,int y)
{
	if(t[p].l>=x && t[p].r<=y)
	{
		return t[p].dat;
	}
	int mid=(t[p].l+t[p].r)>>1;
	int ans=-(0x3f3f3f3f3f3f);
	if(y>mid) ans=max(ans,query(p<<1|1,x,y));
	if(x<=mid) ans=max(ans,query(p<<1,x,y)); 
	return ans;
}
int sum[maxn],k,dp[maxn];
signed main()
{
	cin>>n>>k;
	n+=2;
	a[1]=a[2]=0;
	for(int i=3;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	build(1,1,n);
	int ans=0;
	dp[1]=a[1];
	change(1,1,dp[1]-sum[2]);
	for(int i=2;i<=n;i++)
	{
		int tmp=query(1,max(0,i-k-1),max(0,i-2));
		dp[i]=tmp+sum[i];
		change(1,i,dp[i]-sum[i+1]);
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}
2020/6/3 15:12
加载中...