TopCoder SRM619: EmployManager

まず、候補者が全員不採用の状態からスタートすることを考える。
この時点の利益は 「earning の全要素の合計」にマイナスを掛けたものになる。

候補者 a を不採用から採用へと変更すると

• value[a] の利益が減る
• 他の不採用の候補者 b がいる場合 earning[a][b] 分だけ利益が上がる
• 他の採用の候補者 c がいる場合 earning[a][c] 分だけ利益が上がる

となり、結局のところ他の候補者の採用状況に関係なく

• \(\sum_{i}(\)earning[a][i]\()\) - value[a]

だけ利益が上がる。

よって上記の利益が上がる場合は貪欲に採用していけばよい。

public class EmployManager {
    public int maximumEarnings(int[] value, string[] earning) {
        int n = value.Length;
        int ans = -String.Concat(earning).Sum(c => (int)c - '0') / 2;
        for (int i = 0; i < n; i++) {
            int earn = earning[i].Sum(c => c - '0');
            if (earn - value[i] >= 0) ans += earn - value[i];
        }
        return ans;
    }
}