原题链接

题解

1.观察数据法：看到 \(1e^5\) 想到线性递推，想到遍历每头奶牛试着在它们后面添加隔断时的分组方案数
2.对于奶牛 \(i\) 它的状态转移方程为 \(dp[i]+=dp[j];j<i;sum[j]<=sum[i]\)
3.上述可以把 \(sum\) 看成 x轴， \(dp\) 看成 \(f(x)\)，这样就变成了求小于 \(sum[i]\) 的所有 \(dp[i]\) 的区间求和，而对 \(sum[i]\) 上的 \(dp[i]\) 修改又是单点修改，所以考虑树状数组
4.由于有负数，所以要离散化，注意开头的零也要离散化进去

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
const ll mod=1e9+9;
using namespace std;
ll dp[100005]={0};
ll tree[100005]={0};
ll haxi[100005]={0};
ll n;
ll pre[100005]={0},pre_sort[100005]={0};
ll len=0;

ll query(ll x)
{
    ll sum=0;
    while(x)
    {
        sum+=tree[x];
        sum%=mod;
        x-=lowbit(x);
    }
    return sum;
}

void update(ll x,ll val)
{
    while(x<=len)
    {
        tree[x]+=val;
        tree[x]%=mod;
        x+=lowbit(x);
    }
}

int main()
{
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>pre[i];
        pre[i]+=pre[i-1];
        pre_sort[i]=pre[i];
    }

    sort(pre_sort,pre_sort+1+n);

    len=unique(pre_sort,pre_sort+1+n)-pre_sort;//离散化操作，由于前面的隔断可以选零点后面，所以零点也算上隔断
    for(int i=0;i<=n;i++) haxi[i]=lower_bound(pre_sort,pre_sort+len,pre[i])-pre_sort+1;//离散化，+1代表第几小

    update(haxi[0],1);
    for(ll i=1;i<=n;i++)
    {
        dp[i]=query(haxi[i]);
        update(haxi[i],dp[i]);
    }

    //for(int i=1;i<=n;i++) printf("dp:%d\n",dp[i]);
    cout<<dp[n];
    return 0;
}

//对于每个i，求所有满足presj<presi的dp[j]和，把pres看成下标x，dp看成f(x)，则变成求pres-f(x)
//实际上我们只需要直到pres的相对大小即可，所以把他们离散化