/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
N 個の大きな茶碗が横一列に並んでおり、左から茶碗 0,1,\dots,N-1 と番号付けされています。
茶碗 i ( 1 \le i \le N-1 ) には整数 C_i が書かれており、初めに中には A_i 個の豆が入っています。
茶碗 0 に整数は書かれておらず、初めは豆も入っていません。
以下の操作を繰り返すことを考えます。
- ひとつの茶碗 i ( 1 \le i \le N-1 ) を選び、そこから 1 個以上の豆を取り出す。
- 取り出した豆を、茶碗 i-C_i,i-C_i+1,\dots,i-1 に自由に振り分けて入れる。
- 厳密には、豆を k 個取り出した際、茶碗 i-C_i,i-C_i+1,\dots,i-1 に合計 k 個の豆を入れる。このとき、どの茶碗にいくつ豆を入れるかの振り分け方を任意に指定して入れる。
全ての豆が茶碗 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
例えば以下の 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
例えば以下の 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
Score : 475 points
Problem Statement
There are N large bowls arranged in a row, numbered 0,1,\dots,N-1 from the left.
For each bowl i ( 1\le i\le N-1 ), an integer C_i is written on it, and initially it contains A_i beans.
Bowl 0 has no integer written on it and initially contains no beans.
Consider repeating the following operation any number of times:
- Choose one bowl i (1\le i\le N-1) and take out one or more beans from it.
- Distribute the taken beans freely among bowls i-C_i,i-C_i+1,\dots,i-1.
- Formally, when you take out k beans, you must put a total of k beans into bowls i-C_i,i-C_i+1,\dots,i-1, and you may choose how many beans go into each bowl.
Find the minimum number of operations required to put all the beans into bowl 0.
Constraints
- All input values are integers.
- 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
Input
The input is given from Standard Input in the following format:
N
C_1 C_2 \dots C_{N-1}
A_1 A_2 \dots A_{N-1}
Output
Output the answer as an integer.
Sample Input 1
5 1 1 2 1 1 0 0 1
Sample Output 1
3
For example, the following three operations put all the beans into bowl 0, and this is the minimum:
- Choose bowl 4. It has 1 bean.
- Put 1 bean into bowl 3.
- Choose bowl 3. It has 1 bean.
- Put 1 bean into bowl 1.
- Choose bowl 1. It has 2 beans.
- Put 2 beans into bowl 0.
Sample Input 2
6 1 2 1 3 1 1 1 0 1 1
Sample Output 2
4
For example, the following four operations put all the beans into bowl 0, and this is the minimum:
- Choose bowl 5. It has 1 bean.
- Put 1 bean into bowl 4.
- Choose bowl 4. It has 2 beans.
- Put 1 bean into bowl 1.
- Put 1 bean into bowl 2.
- Choose bowl 1. It has 2 beans.
- Put 2 beans into bowl 0.
- Choose bowl 2. It has 2 beans.
- Put 2 beans into bowl 0.
Sample Input 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
Sample Output 3
7