【NOIP2018模拟赛2018.10.20】抗议

题目

题解

–明显是dp

f[x]：把前x个奶牛按要求分组的方案数

发现要能够转移，j的前缀和要小于等于i的前缀和（j+1~i区间和为非负）

并且要把满足情况的全部加起来

所以可以离散化后用线段树组维护

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+9;

int n,m;
int a[MAXN];
long long s[MAXN],ls[MAXN],c[MAXN];
long long f[MAXN];

void lisan(){
	m=n+1;
	sort(ls+1,ls+1+m);
	m=unique(ls+1,ls+1+m)-ls-1;
	for(int i=0;i<=n;i++)
		s[i]=upper_bound(ls+1,ls+1+m,s[i])-ls-1;
}

void add(int x,long long v){
	for(x;x<=m;x+=x&-x)
		c[x]=(c[x]+v)%mod;
}

long long ask(int x){
	long long ans=0;
	for(x;x;x-=x&-x)
		ans=(ans+c[x])%mod;
	return ans;
}

int main(){
//	freopen("protest.in","r",stdin);
//	freopen("protest.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s[i]=(s[i-1]+1ll*a[i])%mod;
		ls[i+1]=s[i];
	}
	ls[1]=0;
	lisan();
	add(s[0],1);
	for(int i=1;i<=n;i++){
		f[i]=ask(s[i]);
		add(s[i],f[i]);
	}
	cout<<f[n];
	return 0;
}