CF1497D Genius

注意内存限制 $n$个问题从$i$到$n$编号, 第$i$个问题给出 $c_i=2^i$, $tag_i$, $s_i$ 解决问题$i$后解决问题$j$条件是: $IQ

第一行一个$t(1\leq t\leq 100)$, 表示数据组数 每组数据第一行一个$n(1\leq n\leq 5000)$,表示问题个数 第二行$n$个数, 表示$tag_i$ 第三行$n$个数 表示$s_i(1\leq s_i\leq 10^9)$ 保证$\sum n\leq5000$

$t$行, 每行一个数, 表示该组数据最高得分

In the first test case optimal sequence of solving problems is as follows: 1. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 1 $ , after that total score is $ 20 $ and $ \text{IQ} = 6 $ 4. $ 1 \rightarrow 4 $ , after that total score is $ 35 $ and $ \text{IQ} = 14 $ In the second test case optimal sequence of solving problems is as follows: 1. $ 1 \rightarrow 2 $ , after that total score is $ 5 $ and $ \text{IQ} = 2 $ 2. $ 2 \rightarrow 3 $ , after that total score is $ 10 $ and $ \text{IQ} = 4 $ 3. $ 3 \rightarrow 4 $ , after that total score is $ 15 $ and $ \text{IQ} = 8 $ 4. $ 4 \rightarrow 1 $ , after that total score is $ 35 $ and $ \text{IQ} = 14 $ In the third test case optimal sequence of solving problems is as follows: 1. $ 1 \rightarrow 3 $ , after that total score is $ 17 $ and $ \text{IQ} = 6 $ 2. $ 3 \rightarrow 4 $ , after that total score is $ 35 $ and $ \text{IQ} = 8 $ 3. $ 4 \rightarrow 2 $ , after that total score is $ 42 $ and $ \text{IQ} = 12 $