【bzoj2274】[Usaco2011 Feb]Generic Cow Protests dp+树状数组
题目描述
Farmer John's N (1 <= N <= 100,000) cows are lined up in a row andnumbered 1..N. The cows are conducting another one of their strangeprotests, so each cow i is holding up a sign with an integer A_i(-10,000 <= A_i <= 10,000).
FJ knows the mob of cows will behave if they are properly groupedand thus would like to arrange the cows into one or more contiguousgroups so that every cow is in exactly one group and that every group has a nonnegative sum.
Help him count the number of ways he can do this, modulo 1,000,000,009.
By way of example, if N = 4 and the cows' signs are 2, 3, -3, and1, then the following are the only four valid ways of arranging the cows:
(2 3 -3 1)
(2 3 -3) (1)
(2) (3 -3 1)
(2) (3 -3) (1)
Note that this example demonstrates the rule for counting different orders of the arrangements.
给出n个数,问有几种划分方案(不能改变数的位置),使得每组中数的和大于等于0。输出方案数除以 1000000009的余数。
输入
* Line 1: A single integer: N
* Lines 2..N + 1: Line i + 1 contains a single integer: A_i
输出
* Line 1: A single integer, the number of arrangements modulo 1,000,000,009.
样例输入
4
2
3
-3
1
样例输出
4
题解
dp+树状数组
设dp[i]为前i个数的划分方案数。
则易推出dp[i]=∑dp[j](sum[j]≤sum[i],j<i)。
那么可以用树状数组维护sum[j]在区间内的dp[j]的和。
由于sum过大且可能出现非正数,所以要先将sum离散化。
#include <cstdio> #include <algorithm> #define MOD 1000000009 using namespace std; struct data { int sum , p; }a[100010]; int f[100010] , dp[100010] , v[100010] , top; bool cmp1(data a , data b) { return a.sum < b.sum; } bool cmp2(data a , data b) { return a.p < b.p; } void add(int p , int x) { int i; for(i = p ; i <= top ; i += i & (-i)) f[i] = (f[i] + x) % MOD; } int query(int p) { int i , ans = 0; for(i = p ; i ; i -= i & (-i)) ans = (ans + f[i]) % MOD; return ans; } int main() { int n , i , t; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &t) , a[i].sum = a[i - 1].sum + t , a[i].p = i; sort(a , a + n + 1 , cmp1); v[0] = 0x80000000; for(i = 0 ; i <= n ; i ++ ) { if(a[i].sum != v[top]) v[++top] = a[i].sum; a[i].sum = top; } sort(a , a + n + 1 , cmp2); dp[0] = 1; add(a[0].sum , 1); for(i = 1 ; i <= n ; i ++ ) dp[i] = query(a[i].sum) , add(a[i].sum , dp[i]); printf("%d\n" , dp[n]); return 0; }
相关文章
- php 数组操作
- php打乱数组二维数组、多维数组
- ajax传递数组,后台更新
- Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)
- Java实现 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
- Java实现最大连续子数组和
- (笔试题)将数组分成两组,使两组的和的差的绝对值最小
- 使用选择排序对一维数组进行排序
- C语言变长数组data[0]【总结】
- Leetcode0307. 区域和检索 - 数组可修改(medium)
- JavaSE进阶 | 一维数组的定义、使用和数组扩容
- Leetcode 2176. 统计数组中相等且可以被整除的数对
- Leetcode 1013. 将数组分成和相等的三个部分(终于解决)
- Leetcode 2210. 统计数组中峰和谷的数量(可以,已解决)
- c语言输出十六进制字节数组
- JAVA数组的定义及用法
- poj - 1159 - Palindrome(滚动数组dp)
- 结构体数组
- 树状数组 Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains
- 【数据结构与算法】线性表--数组
- Java(3):Java语言中的数组