a193. NOI2008 Day1.3.志愿者招募 - 高中生程式解題系統

內容

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的
主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志
愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。
布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工
作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的
工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是
布布找到了你，希望你帮他设计一种最优的招募方案。

輸入說明

输入文件的第一行包含两个整数N, M，表示完成项目的天数和
可以招募的志愿者的种类。
接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。
接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起
见，我们可以认为每类志愿者的数量都是无限多的。

輸出說明

输入文件中仅包含一个整数，表示你所设计的最优方案的总费用。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 2.0s , <1K
公開測資點#1 (10%): 2.0s , <1K
公開測資點#2 (10%): 2.0s , <1K
公開測資點#3 (10%): 2.0s , <1M
公開測資點#4 (10%): 2.0s , <1M
公開測資點#5 (10%): 2.0s , <1M
公開測資點#6 (10%): 2.0s , <1M
公開測資點#7 (10%): 2.0s , <1M
公開測資點#8 (10%): 2.0s , <1M
公開測資點#9 (10%): 2.0s , <1M

提示：

【样例说明】
招募 3 名第一类志愿者和4 名第三类志愿者。

【数据规模和约定】
30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10；
100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均
不超过2^31-1。

標籤:

出處:

NOI 2008 Day1 第三题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」