【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;
}