# APCS實作題2020年10月第1題：人力分配

> 日期：2023年9月10日
> 作者：王一哲
> 題目來源：109年10月實作題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f312)

<br />

## 題目

### 問題描述

有一個公司有 $n$ 個員工，還有兩個工廠。如果工廠一與工廠二分別有 $X_1$ 與 $X_2$ 個員工，兩個工廠的收益 $Y_1$、$Y_2$ 分別會是
$$
Y_1 = A_1 X_1^2 + B_1 X_1 + C_1 \\
Y_2 = A_2 X_2^2 + B_2 X_2 + C_2
$$
請你考慮所有分配員工的方式，找出收益最大的組合，輸出最大收益。注意，每個員工皆需分配到其中一個工廠。
<br />

### 輸入格式

第一行有三個整數 $A_1, B_1, C_1$，第二行有三個整數 $A_2, B_2, C_2$，第三行有一個正整數 $n$ ($1 \leq n \leq 100$)。

配分
- 50分：$n = 2$
- 50分：$1 \leq n \leq 100$
<br />

### 輸出格式

輸出最大收益
<br />

### 範例：輸入

2 -1 3
4 -5 2
2

### 範例：正確輸出

11

<br />

## Python 程式碼

解題時要注意，**可以不分配人力到其中一間工廠，收益有可能是負數**。於 ZeroJudge 測試結果，最長運算時間約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。

import sys

A1, B1, C1 = map(int, input().split())
A2, B2, C2 = map(int, input().split())
n = int(input())
ans = -sys.maxsize - 1
for i in range(0, n+1):
    Y1 = A1*i*i + B1*i + C1
    Y2 = A2*(n-i)*(n-i) + B2*(n-i) + C2
    ans = max(ans, Y1+Y2)
    
print(ans)

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 6 ms，使用記憶體最多約為 340 kB，通過測試。

#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;

int main() {
    long A1, B1, C1, A2, B2, C2, n;
    cin >> A1 >> B1 >> C1;
    cin >> A2 >> B2 >> C2;
    cin >> n;
    long ans = INT_MIN;
    
    for(long i=0; i<=n; i++) {
        long Y1 = A1*i*i + B1*i + C1;
        long Y2 = A2*(n-i)*(n-i) + B2*(n-i) + C2;
        ans = max(ans, Y1+Y2);
    }
    
    cout << ans << endl;
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`