[COCI 2014-2015 #7] ACM(ACM Task Assignment)

题目描述

Zagreb 大学的团队的成员 Stjepan、Ivan 和 Gustav 正在摩洛哥参加 ACM 国际大学生程序设计竞赛的世界决赛。他们的技术指导 Goran 想出了一个无敌的策略，用于解决决赛中的题目。

在一开始，每个团队成员迅速估计 $n$ 道题目中每题的难度。这些难度用 $1$ 到 $5$ 的数字描述，数字越大，难度也就越大。

在这之后，他们之间将分配任务。为了简单起见，任务阵列将被分成三部分，以便每个团队成员得到一个非空的连续任务序列来思考。这种分配是为了使估计的难度之和最小，而只计算被分配到该任务的团队成员的估计难度值。你的任务是计算这个最小的可能总和。

输入格式

输入共四行。

第一行输入一个整数 $n$，表示问题的数量。
第二到第四行，第 $i+1$ 行 $n$ 个整数 $d_{i,1},d_{i,2},\dots,d_{i,n}$，表示第 $i$ 号成员对于这 $n$ 道题目估计的难度。

输出格式

输出仅一行，一个整数，表示最小可能的估计难度总和。

样例输入 #1

3
1 3 3
1 1 1
1 2 3

样例输出 #1

4

样例输入 #2

7
3 3 4 1 3 4 4
4 2 5 1 5 5 4
5 5 1 3 4 4 4

样例输出 #2

19

数据范围

【样例 1 解释】

给第 $1$ 号成员分配第 $1$ 题，给第 $2$ 号成员分配第 $3$ 道题，给第 $3$ 号成员分配第 $2$ 道题。这样分配的难度总和为 $1+1+2=4$。可以证明没有难度总和更小的分配方案。

【数据范围】

对于所有数据，$3\leqslant n\leqslant 1.5\times 10^5$，$1\leqslant d_{i,j}\leqslant 5$。

【题目来源】

本题来源自 COCI 2014-2015 CONTEST 7 T3 ACM，按照原题数据配置，满分 $100$ 分。

由 Eason_AC 翻译整理提供。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1250。

测试点分布

出处：原题链接