分数: 475 点
问题陈述
有 N 大碗排成一排,编号 0,1,\dots,N-1 从左边开始。
每个碗 i ( 1\le i\le N-1 ),一个整数
上面写着 C_i ,最初它包含 A_i 豆类。
碗 0 上没有写入任何整数,并且最初不包含任何 bean。
考虑重复以下操作任意次:
- 选择一碗 i (1\le i\le N-1)并从中取出一颗或多颗豆子。
- 将取出的豆子自由地分布在碗中 i-C_i,i-C_i+1,\dots,i-1.
- 正式来说,当您取出 k 豆子,您总共必须放入 k 豆子装入碗中 i-C_i,i-C_i+1,\dots,i-1,您可以选择每个碗里放入多少豆子。
求将所有豆子放入碗中所需的最少操作次数 0.
约束
- 所有输入值均为整数。
- 2 \le N \le 2000
- 1 \le C_i \le i
- 0 \le A_i \le 1
- \displaystyle \sum_{i=1}^{N-1} A_i > 0
输入
输入由标准输入按以下格式给出:
N
C_1 C_2 \dots C_{N-1}
A_1 A_2 \dots A_{N-1}
输出
将答案输出为整数。
示例输入 1
5 1 1 2 1 1 0 0 1
示例输出 1
3
例如以下三个操作将所有的豆子放入碗中 0,这是最小值:
- 选择碗 4。它有 1 豆。
- 把 1 豆入碗 3.
- 选择碗 3。它有 1 豆。
- 把 1 豆入碗 1.
- 选择碗 1。它有 2 豆类。
- 把 2 豆子入碗 0.
示例输入 2
6 1 2 1 3 1 1 1 0 1 1
示例输出 2
4
例如以下四个操作将所有的豆子放入碗中 0,这是最小值:
- 选择碗 5。它有 1 豆。
- 把 1 豆入碗 4.
- 选择碗 4。它有 2 豆类。
- 把 1 豆入碗 1.
- 把 1 豆入碗 2.
- 选择碗 1。它有 2 豆类。
- 把 2 豆子入碗 0.
- 选择碗 2。它有 2 豆类。
- 把 2 豆子入碗 0.
示例输入 3
16 1 1 1 2 5 1 1 3 4 1 4 3 1 1 2 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1
示例输出 3
7