소객 매일 한 문제 3 수학 시험 문제풀이(접두사와 +dp)

제목 링크

제목의 대의.

두 단락의 불연속 구간을 구하여 최대로 하다

제목 사고방식

전언

제목 데이터를 보는 첫 순간에 o(n)의 복잡도만 있을 수 있다고 생각했지만 o(nlogn)도 될 수 있을 것 같았다. 그리고 나의 모색을 통해 라인 트리로 o(nlogn)의 복잡도를 칠 수 있다는 것을 발견하고 t가 되었다.일단 t 코드를 넣고 데이터 범위를 조금 좁히면 넘길 수 있을 것 같아요.

#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int t,n,k,a[maxn];
ll tree[maxn<<2],qz[maxn],sum[maxn],ans=-inf;
void update(int node,int l,int r,int pos,ll zhi){
	if(l==r){
		tree[node]=zhi;
		return ;
	}
	int mid=(l+r)/2;
	if(mid>=pos)	update(node<<1,l,mid,pos,zhi);
	else			update(node<<1|1,mid+1,r,pos,zhi);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
ll query(int node,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return tree[node];
	} 
	ll ans=-inf,mid=(l+r)/2;
	if(mid>=L)	ans=max(ans,query(node<<1,l,mid,L,R));
	if(mid

본문

길이가 이미 알려졌기 때문에 가장 폭력적인 방법은 두 개의 서브 구간의 기점을 직접 매거한 다음에 화합을 구하는 것이다. 복잡도 O(n^2*k)의 연속 구간 구화는 접두사와 화합으로 최적화할 수 있다. 즉sum[i]로 수열 전 i의 숫자의 합을 표시하면sum[i]=sum[i-1]+a[i]이고 구간 [l,r]의 합은sum[r]-3m[l-3]로 표시할 수 있다.이렇게 최적화된 후에 두루 화합하지 않고 직접 계산하면 된다. 시간의 복잡도는 O(n^2)로 변한다. 실제로 우리는 오른쪽 자구간의 출발점을 열거하지 않는다. 만약에 우리가 선택한 왼쪽의 이 구간이 [l,r]라면 오른쪽의 구간은 r오른쪽의 길이가 k인 구간 안과 가장 큰 것이기 때문이다.이것은 오른쪽에서 왼쪽으로 한 번 스캔만 하면 유지될 수 있습니다. 만약에 우리가 maxn[i]로 i 오른쪽의 모든 길이가 k인 구간의 화의 최대치를 표시한다면 maxn[i]=max(maxn[i+1],sum[i+k-1]--sum[i-1])(i+1 오른쪽 길이가 k인 구간의 최대치이거나 i부터 오른쪽 길이가 k인 구간)의 최대치입니다.이렇게 됐어.

코드

#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int t,n,k,a[maxn];
ll sum[maxn],houmax[maxn],ans;
void init(){
	ans=-inf;
	memset(houmax,-0x3f,sizeof(houmax));
}
int main(){
	scanf("%d",&t);
	while(t--){
		init();
		scanf("%d %d",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		for(int i=n-k+1;i>=1;i--){//houmax[i]   i         k          
			houmax[i]=max(houmax[i+1],sum[i+k-1]-sum[i-1]);
		}
		for(int i=1;i+2*k-1<=n;i++){//   i+2*k-1,      [i,i+k-1],     [i+k,i+2*k-1] 
			ans=max(ans,sum[i+k-1]-sum[i-1]+houmax[i+k]);
		}
		printf("%lld
",ans);
	}
	return 0;
}

변형 문제

1: 길이를 제한하지 않음 - 한 수열에서 두 개의 서로 교차하지 않는 구간을 찾아 그들의 권한과 최대 2: 구간의 수를 증가시킨다. - m개의 길이가 k인 서로 교차하지 않는 구간을 찾아 그들의 권한과 최대 (1≤n≤5000) 3: 구간의 수가 많고 길이를 제한하지 않는다. - m개의 서로 교차하지 않는 길이를 찾아 그들의 권한과 최대 (1≤n≤5000)

변형 1

일단 비둘기, 비둘기, 비둘기.
참조 링크https://ac.nowcoder.com/discuss/392146