軍隊派遣問題

軍隊派遣人力不可低於需求人力，派遣與調回需要花費金錢， 常駐的也需要花錢。派遣當月需要給付常駐補給費，調回不須。 給予一個陣列A代表每個月的人力需求，求最低預算。

格式

第一行四個值:

第二行為每月所需人數。

範例

測資一

4 22 14 84
10 4 14 10

測資一結果: 980

測資二

3 21 13 84
10 11 12

測資二結果: 681

測資三

3 21 13 84
13 14 15

測資三結果: 861

測資四

7 10 20 30
3 7 4 5 1 8 9

測資四結果: 1050

解法

透過dp動態規劃下去處理，計算一個月當中所有可能派遣與調回的情況，以及 沒有變化的情況，用上次最小值作為當前計算的基底， 迭代的時候求出每次最小值。

程式碼

原先複雜度是O(max(A)*n)，觀察兩個測資發現似乎可以壓到O(n)

測資一

7 10 20 30
3 7 4 5 1 8 9
   x    x    x    x    x    x    x  270  300  330
   x    x    x    x  440  430  420  410  440  470
   x    x    x    x    x  570  560  550  580  610
   x  750  740  730  720  710  700  690  720  750
   x    x    x    x    x    x    x    x  860  890
   x    x    x    x    x    x    x    x    x 1050
1050

測資二

7 10 20 30
3 7 4 5 1 8 12
   x    x    x    x    x    x    x  270  300  330  360  390  420
   x    x    x    x  440  430  420  410  440  470  500  530  560
   x    x    x    x    x  570  560  550  580  610  640  670  700
   x *750**740* 730  720  710  700  690  720  750  780 *810**840*
   x    x    x    x    x    x    x    x  860  890  920  950  980
   x    x    x    x    x    x    x    x    x    x    x    x 1140
1140

第一次優化

觀察後發現或許子迴圈超過3個值時可以抓取兩側， 算出兩個線性方程式，透過交點找到周圍的最小值， 無解就表示兩側有一邊是最小值，透過斜率判斷左邊右邊。

為了確定是不是線性函數

solve = dp[i - 1][pre_people] + y * j + z * -(j - pre_people)
solve = dp[i - 1][pre_people] + y * j + x * (j - pre_people)

展開之後重新分配可以得到

solve = (dp[i - 1][pre_people] + z * pre_people) + (y - z) * j
solve = (dp[i - 1][pre_people] - x * pre_people) + (y + x) * j

確定是線性(其實不重新分配好像也看得出現性)

測資三

7 10 30 20
3 7 4 5 1 8 12
   x    x    x    x    x    x    x  370  410  450  490  530  570
   x    x    x    x  550  560  570  580  620  660  700  740  780
   x    x    x    x    x  710  750  790  830  870  910  950  990
   x  820  830  840  850  860  900  940  980 1020 1060 1100 1140
   x    x    x    x    x    x    x    x 1130 1170 1210 1250 1290
   x    x    x    x    x    x    x    x    x    x    x    x 1530
1530

y - z有可能是正或負，可能還需要考慮這種情況 ，合理的情況y + x恆正(假設花費金額都為正數)，這個時候就是最左側。

第二次優化

應該可以從這個程式碼 看出來，是不會有斷層，找交點好像也是多餘的。 因為交點是根據diff判斷出來，似乎拿上一次的人數來找似乎更簡單。 可以畫一條斜線，然後畫一個點當作交點(diff)，交點左側可以大於 或小於原本直線的值，右側則大於等於。

diff = j - pre_people

反正任意切，只有左邊小於的情況會在最左側，大於等於的情況會接近diff。

優化結論

第一次優化

第二次優化

程式碼

Dynamic programming