#P1513. 2023.08.30-HW秋招第二场-第三题-内存分配

2023.08.30-HW秋招第二场-第三题-内存分配

题目描述

系统由nn个任务组成,任务运行有依赖关系,前序任务执行完毕才可以启动后续任务。任务在启动前申请内存,执行完毕后释放,内存释放后可用于其他任务使用。解除依赖后的任务会直接由操作系统调度,分配内存,进入运行状态。每个任务的运行时间相等。请计算系统所有任务执行所需要的最小内存。

输入

11行为11个正整数nn,表示任务个数,n<20n<20

22行为nn个正整数,表示每个任务所需要的内存大小,0<内存<10000<内存<1000

33行为nn个取值为0011的数,表示任务00对其他任务的依赖关系,00表示不依赖,11表示依赖

....

3+n3+n行为nn个取值为0011的数,表示任务n1n-1对其他任务的依赖关系,00表示不依赖,11表示依赖

输出

输出系统任务执行所需要的最小内存

样例

输入

9
50 50 80 40 40 40 60 60 60
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0

输出

120

解释

第一行:99,表示有99个任务 第二行: 5050 5050 8080 4040 4040 4040 6060 6060 6060,表示任务t0 08t0~08需要的内存大小

第三行:00 00 00 00 00 00 00 00 00,表示tt不依赖任务其他任务 第四行:1010 00 00 00 00 00 00 00,表示t1t1依赖t0t0

第五行:0101 00 00 00 00 00 00 00,表示t2t2依赖t1t1

~

任务的关系用图表示

40 60
t4 t6
50 80 40 60
t0 t1 t2 t3 t7 t8
40
t5
  1. 执行t0t0,分配m0=50m0=50,占用空间[0,50)[0,50),最大访问地址为5050
  2. 执行t1t1,分配m1=50m1=50,占用空间[0,50)[0,50),最大访问地址为5050
  3. 并发执行t2t2t5t5,分配m2=80m2=80m5=40m5=40,占用空间[0,120)[0,120),最大访问地址为120
  4. 执行t3t3,分配m3=40m3=40,占用空间[0,40)[0,40),最大访问地址4040
  5. 并发执行t4t4t7t7,分配m4=40m4=40m7=60m7=60,占用空间[0,100)[0,100)
  6. 执行t6t6,分配m6=60m6=60,占用空间[0,60)[0,60),最大访问地址6060
  7. 执行t8t8,分配m8=60m8=60,占用空间[0,60)[0,60),最大访问地址6060

输出系统的需要的最小内存为120120

样例2

输入

10
40 50 80 10 30 80 90 30 70 150
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

输入

190