P1569 [USACO11FEB]属牛的抗议Generic Cow Prote…

    • 330通过
    • 1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp USACO 2011
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Farmer John's N (1 <= N <= 100,000) cows are lined up in a row and numbered 1..N. The cows are conducting another one of their strange protests, 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 grouped and thus would like to arrange the cows into one or more contiguous groups 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, and 1, 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头奶牛聚集在一起,排成一列,正在进行一项抗议活动。第i头奶牛的理智度 为Ai,Ai可能是负数。约翰希望奶牛在抗议时保持理性,为此,他打算将所有的奶牛隔离成 若干个小组,每个小组内的奶牛的理智度总和都要大于零。由于奶牛是按直线排列的,所以 一个小组内的奶牛位置必须是连续的。 请帮助约翰计算一下,最多分成几组。

    输入输出格式

    输入格式:

    第1行包含1个数N,代表奶牛的数目。

    第2至N+1行每行1个整数Ai。

    输出格式:

    输出文件有且仅有一行,包含1个整数即为最多组数。

    若无法满足分组条件,则输出Impossible。

    输入输出样例

    输入样例#1: 复制
    4
    2
    3
    -3
    1
    
    输出样例#1: 复制
    3

    说明

    【数据规模和约定】

    30%的数据满足N≤20。

    100%的数据满足N≤1000,|Ai|≤100000。

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