洛谷2344 奶牛*（DP+BIT+离散化）

洛谷2344 奶牛*

本题地址：http://www.luogu.org/problem/show?pid=2344

题目背景

Generic Cow Protests, 2011 Feb

题目描述

约翰家的N 头奶牛正在排队游行*。一些奶牛情绪激动，约翰测算下来，排在第i 位的奶牛的理智度为Ai，数字可正可负。
约翰希望奶牛在*时保持理性，为此，他打算将这条队伍分割成几个小组，每个*小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛必须是连续位置的。除此之外，分组多少组，每组分多少奶牛，都没有限制。
约翰想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。

输入输出格式

输入格式：

• 第一行：单个整数N，1 ≤ N ≤ 100000
• 第二行到第N + 1 行：第i + 1 行有一个整数Ai，−10^5 ≤ Ai ≤ 10^5

输出格式：

单个整数：表示分组方案数模1000000009 的余数

输入输出样例

输入样例#1：

4

2

3

-3

1

输出样例#1：

4

说明

解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。

【思路】

线性DP+BIT加速+离散化。

设d[i]表示前i头奶牛的分法，则有转移方程式如下：

d[i]=sigma{ d[j]( j<i && S(j+1,i)>=0 ) }

其中sigma表示求和、S代表区间和。

如果令sum[]表示前缀和，则可以进一步得出转移条件：存在j<i且sum[j]<=sum[i]

 BIT加速：如果DP枚举到i，令C[x]表示i之前sum==x的所有d之和，则d[i]为小于sum[i]的所有d之和，可以用BIT求出小于sum[i]的区间和。

  离散化：sum的情况最多有n+1种而其范围可能很大，所以考虑对sum进行离散化。

另外有0的情况可以考虑将BIT下标进行偏移或hash到其他范围。

【代码】

 #include<cstdio>
 #include<iostream>
 #include<algorithm>
 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
 using namespace std;

 const int maxn = +;
 const int MOD=;

 int sum[maxn],a[maxn];
 int hash[maxn],cnt;
 int n;

 int C[maxn],Max;
 int lowbit(int x) { return x&(-x); }
 int Sum(int x) {
     x++;
     int res=;
     while(x>) {
         res = (res+C[x])%MOD;
         x-=lowbit(x);
     }
     return res;
 }
 void Add(int x,int v) {
     x++;
     while(x<=Max+) {
         C[x] = (C[x]+v)%MOD;
         x+=lowbit(x);
     }
 }

 int find(int x) {
     return lower_bound(hash,hash+cnt+,x)-hash;
 }

 int main() {
     scanf("%d",&n);
     FOR(i,,n) {
         scanf("%d",&a[i]);
         sum[i]=sum[i-]+a[i];
         Max=max(Max,sum[i]);
     }
     sort(sum,sum+n+);         //将0计入
     hash[]=sum[];
     FOR(i,,n) if(sum[i]!=sum[i-]) {
         hash[++cnt]=sum[i];
     }
     Add(find(),);
     int tot=,ans=;
     FOR(i,,n) {
         tot += a[i];
         ans = Sum(find(tot))%MOD;
         Add(find(tot),ans);
     }
     printf("%d\n",ans);
     return ;
 }