Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
独立任务最优调度问题
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 21, Accepted users: 15
Problem 10269 : No special judgement
Problem description
  用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai ,若 由机器B 来处理,则需要时间bi 。由于各作业的特点和机器的性能关系,很可能对于某些i, 有ai ≥ bi ,而对于某些j,j≠i,有aj < bj 。既不能将一个作业分开由2 台机器处理,也 没有一台机器能同时处理2 个作业。设计一个动态规划算法,使得这2 台机器处理完这n 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例: (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。

Input
  第1行是1个正整数n, 表示要处理n个作业。 接下来的2行中,每行有n 个正整数,分别表示处理机A 和B 处理第i 个作业需要的处理时 间。

Output
  程序运行结束时,将计算出的最短处理时间输出

Sample Input
6
2 5 7 10 5 2
3 8 4 11 3 4
Sample Output
15
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:18304 today,16241295 total, since 2010-05-07