本文主要是介绍洛谷 P2344 奶牛抗议 (树状数组+DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目背景
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[i]为前i个奶牛可以分的方案数,现在想想它的状态转移方程。
我们可以这样考虑,第i个奶牛对答案是怎么贡献的。显然i可以和i-1分成一组,可以和i-1,i-2分成一组...以此类推。
所以我们只要能这样分成了一组,那么这组的方案数就是dp[j]。
于是我们得到了状态转移方程:
条件是
这个累加的和,我们可以用树状数组来求得。
而因为sum数组的值过于大,我们需要离散化,防止下标对答案造成的影响我们需要去重。
完成了以上操作后,我们又按下标从小到大排序使其满足
用树状数组统计的值即满足第二个条件,所以得到的答案就是dp[i],再添加了dp[i]后,继续往后推,直到推到dp[n]即为所求。
注意:
有一个特殊点那就是,这是表示它本身分成一组,方案数为1,所以对于这个点。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn=1e5+5;
const int mod=1e9+9;
typedef long long ll;
struct node
{ll sum;int id;int v;
}q[maxn];
bool cmp1(node a,node b)
{return a.sum<b.sum;
}
bool cmp2(node a,node b)
{return a.id<b.id;
}
int c[maxn];
int lowbit(int i)
{return i&(-i);
}
void update(int x,int add)
{while(x<maxn){c[x]=(c[x]+add)%mod;x+=lowbit(x);}
}
int query(int x)
{int ans=0;while(x){ans=(ans+c[x])%mod;x-=lowbit(x);}return ans;
}
int main()
{int n;scanf("%d",&n);q[0].id=0,q[0].sum=0;for(int i=1;i<=n;i++){scanf("%lld",&q[i].sum);q[i].sum=q[i].sum+q[i-1].sum;q[i].id=i;}sort(q,q+1+n,cmp1);q[0].v=1;int cnt=1;for(int i=1;i<=n;i++){if(q[i].sum==q[i-1].sum)q[i].v=cnt;elseq[i].v=++cnt;}sort(q,q+1+n,cmp2);int ans=0;update(q[0].v,1);for(int i=1;i<=n;i++){ans=query(q[i].v);//询问前为dp[i],插入后就不满足j<i了。update(q[i].v,ans);}printf("%d\n",ans);return 0;
}
这篇关于洛谷 P2344 奶牛抗议 (树状数组+DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!