P2344 奶牛抗议

    • 336通过
    • 1.1K提交
  • 题目提供者 wwqk4444
  • 评测方式 云端评测
  • 标签 前缀和 动态规划,动规,dp 树状数组 离散化 USACO
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    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

    说明

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。