USACO2011FEB GOLD 奶牛抗议

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Sun Oct 28 14:31:41 CST 2018

In Category: NoCategory

Description：

给 $n$ 个数，把他们划分成一些段使得每段和非负，问方案数。

$1\leqslant n\leqslant 10^5$

Solution：

先列直接的转移方程，即： $$ f[i]=\sum_{k=1}^{i-1}f[k](s[i]-s[k]\geqslant 0) $$ 其实是一个二维偏序，离散化 $+$ 树状数组。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN],s[MAXN];

int b[MAXN];

int c[MAXN];

int lowbit(int x){return x & (-x);}

#define MOD 1000000009

int tot;

void add(int p,int x){for(int i = p;i <= tot;i += lowbit(i))c[i] = (c[i] + x) % MOD;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = (res + c[i]) % MOD;return res;}

int f[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)b[i] = s[i] = s[i - 1] + a[i];

	b[n + 1] = 0;

	sort(b + 1,b + 1 + n + 1);

	tot = unique(b + 1,b + 1 + n + 1) - b - 1;

	for(int i = 0;i <= n;++i)s[i] = lower_bound(b + 1,b + 1 + tot,s[i]) - b;

	add(s[0],1);

	for(int i = 1;i <= n;++i)

	{

		f[i] = query(s[i]);

		add(s[i],f[i]);

	}

	cout << f[n] << endl;

	return 0;

}

In tag: DP-计数DP 数据结构-树状数组

wjh15101051