프로그램 명: coci_jedan
제한시간: 1 초
N개의 음이 아닌 정수들로 이루어진 수열이 있다.
이런 수열 중 첫 항과 마지막 항은 0이고, 수열의 인접한 두 항의 차이는 항상 0 또는 1인 것을 연속 수열이라고 하자.
주어진 수열 C에서 몇 개의 부분은 빈칸으로 구성되어 있다. 이 때, 빈칸에 수를 넣어서 연속 수열을 만드는 방법의 수를 구하는 프로그램을 작성하여라.
입력 형식
-
첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 10,000)
-
두 번째 줄에는 C1 에서부터 CN 까지 순서대로 주어진다. 단, 각 수는 -1 이상 10,000 이하이며, -1은 빈칸을 의미한다.
출력 형식
빈칸에 수를 넣어서 연속 수열을 만드는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
Some people like to pretend that they are a pharaoh. Or a dolphin. Luka is one such person.
He has built a relief consisting of a long line of N columns with nonnegative integer heights. The
heights of all columns were initially zero. The relief was build in steps, where in each step Luka would
select a contiguous subsequence of columns with equal heights and raise all columns in the
subsequence, except the first and last column, by one.
Hundreds of years have passed, and some of the columns have been stolen. Luka's great-great-...-
great-grandson is trying to determine the number of possible reliefs that could have been built by Luka
such that the remaining columns' heights match the original relief.
입력
The first line of input contains the positive integer N (1 ≤ N ≤ 10 000), the number of columns in
Luka's relief.
The second line of input contains N space-separated integers hi
(-1 ≤ hi ≤ 10 000), the column heights.
A height of -1 represents a stolen column.
출력
The first and only line of output must contain the required number of possible reliefs modulo 1 000
000 007.
입출력 예
input
3
-1 2 -1
output
0
input
3
-1 -1 -1
output
2
input
6
-1 -1 -1 2 -1 -1
output
3
출처:coci/2012-2013/contest6
번역:functionx
[질/답]
[제출 현황]
[푼 후(2)]