noi2017-Day2-T2

【問題描述】

小N是蔬菜倉庫的管理員，負(fù)責(zé)設(shè)計(jì)蔬菜的銷售方案。
在蔬菜倉庫中，共存放有n種蔬菜，小N需要根據(jù)不同蔬菜的特性，綜合考慮各方面因素，設(shè)計(jì)合理的銷售方案，以獲得最多的收益。
在計(jì)算銷售蔬菜的收益時(shí)，每銷售一個(gè)單位第i種蔬菜，就可以獲得ai的收益。
特別地，由于政策鼓勵(lì)商家進(jìn)行多樣化銷售，第一次銷售第i種蔬菜時(shí)，還會(huì)額外得到si的額外收益。
在經(jīng)營(yíng)開始時(shí)，第i種蔬菜的庫存為ci個(gè)單位。
然而，蔬菜的保鮮時(shí)間非常有限，一旦變質(zhì)就不能進(jìn)行銷售，不過聰明的小N已經(jīng)計(jì)算出了每個(gè)單位蔬菜變質(zhì)的時(shí)間 ：對(duì)于第i種蔬菜，存在保鮮值xi，每天結(jié)束時(shí)會(huì)有xi個(gè)單位的蔬菜變質(zhì)，直到所有蔬菜都變質(zhì)。（注意：每一單位蔬菜的變質(zhì)時(shí)間是固定的，不隨銷售發(fā)生變化）
形式化地：對(duì)于所有的滿足條件d * xi <= ci的正整數(shù)d,有xi個(gè)單位的蔬菜將在第d天結(jié)束時(shí)變質(zhì)。
特別地，若(d-1)xi <= ci < dxi,則有ci - (d - 1)*xi單位的蔬菜將在第d天結(jié)束時(shí)變質(zhì)。
注意，當(dāng) xi=0時(shí)，意味著這種蔬菜不會(huì)變質(zhì)。
同時(shí)，每天銷售的蔬菜總量也是有限的，最多不能超過m個(gè)單位。
現(xiàn)在，小N有k個(gè)問題，想請(qǐng)你幫忙算一算。每個(gè)問題的形式都是：對(duì)于已知的pj，如果需要銷售pj天，最多能獲得多少收益？
（題目描述以pdf文件為準(zhǔn)）

【輸入形式】

從文件 vegetables.in 中讀入數(shù)據(jù)。 第一行包含三個(gè)正整數(shù) n, m, k,分別表示蔬菜的種類數(shù)目、每天能售出蔬菜總量上限、小 N 提出的問題的個(gè)數(shù)。 接下來 n 行,每行輸入四個(gè)非負(fù)整數(shù),描述一種蔬菜的特點(diǎn),依次為 a i , s i , c i , x i ,意義如上文所述。 接下來 k 行,每行輸入一個(gè)非負(fù)整數(shù) p j ,意義如上文所述。

【輸出形式】

輸出到文件 vegetables.out 中。 輸出 k 行,每行包含一個(gè)整數(shù),第 i 行的數(shù)表示第 i 個(gè)問題的答案。

【輸入樣例1】

見下發(fā)文件的 vegetables/vegetables1.in。

【輸出樣例1】

見下發(fā)文件的 vegetables/vegetables1.ans。

【輸入樣例2】

見下發(fā)文件的 vegetables/vegetables2.in。

【輸出樣例2】

見下發(fā)文件的 vegetables/vegetables2.ans。

【輸入樣例3】

見下發(fā)文件的 vegetables/vegetables3.in。

【輸出樣例3】

見下發(fā)文件的vegetables/vegetables3.ans。

【時(shí)間限制】

3s

【空間限制】

512000KB

【上傳文件】

上傳c, cpp, pas語言源程序，文件名為vegetables.c, vegetables.cpp, vegetables.pas。

Upload Your source File(s) :

Note :Your program can be written with the programing language(s) as below
C(.c): your source filename is ''vegetables.c''
CPP(.cpp): your source filename is ''vegetables.cpp''
PAS(.pas): your source filename is ''vegetables.pas''

我知道是用貪心的策略，
但無論是單獨(dú)貪心多賣還是單獨(dú)貪心高價(jià)明顯都會(huì)有對(duì)應(yīng)的數(shù)據(jù)卡分，
明智的貪心顯然會(huì)是其他辦法,我暫時(shí)沒有思路，做過類似的例題，模擬賽中一時(shí)記不得了