← 返回题目列表

AtCoder · abc404_e

H. 碗和豆子

中文机器翻译题面 查看原题

分数: 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