P4302 - 移动硬币

有一个无限的递减(非增)非负数组a(有限项不为0)，索引从0开始。另外有一个无限的矩阵，左上角为(0,0)。对于矩阵的一个位置(x,y)，如果y <a_x，则这个位置为白色，否则为黑色。给定一个数组a，表示无限数组的若干项，后面的项都是0。现在左上角有一个硬币。每次操作可以选择一个硬币，拿走，然后往它的右边和下边各放置一个硬币。问最少需要多少次操作，可以将硬币全部移出白色的格子。
答案对1e9+7取模

第一行一个整数n (1≤n≤2⋅10⁵)
第二行n+1个递减整数a₀,a₁,....,a_n (0≤a_i≤2⋅10⁵)

一个整数代表操作数，对1e9+7取模

2
2 2 0

第一个样例解释：
Consider the first example. In the given grid, cells (0,0),(0,1),(1,0),(1,1) are white, and all other cells are black. Let us use triples to describe the grid: triple (x,y,z)means that there are z dolls placed on cell (x,y). Initially the state of the grid is (0,0,1).

One of the optimal sequence of operations is as follows:

Do the operation with (0,0). Now the state of the grid is (1,0,1),(0,1,1).
Do the operation with (0,1). Now the state of the grid is (1,0,1),(1,1,1),(0,2,1).
Do the operation with (1,0). Now the state of the grid is (1,1,2),(0,2,1),(2,0,1).
Do the operation with (1,1). Now the state of the grid is (1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1).
Do the operation with (1,1). Now the state of the grid is (0,2,1),(2,0,1),(1,2,2),(2,1,2).

Now all white cells contain 0 dolls, so we have achieved the goal with 5 operations.

4302: 移动硬币

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示