Q28 クラブ活動への最適な配分

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    struct ClubInfoDef
    {
        internal int Hirosa;
        internal int Buinsuu;
    }

    static void Main()
    {
        var ClubInfoList = new List<ClubInfoDef>();
        Action<int, int> AddAct = (pHirosa, pBuinsuu) =>
            ClubInfoList.Add(new ClubInfoDef() { Hirosa = pHirosa, Buinsuu = pBuinsuu });

        AddAct(11000, 40);
        AddAct(8000, 30);
        AddAct(400, 24);
        AddAct(800, 20);
        AddAct(900, 14);
        AddAct(1800, 16);
        AddAct(1000, 15);
        AddAct(7000, 40);
        AddAct(100, 10);
        AddAct(300, 12);

        //最大の面積[部員数]なDP表
        const int UB = 150;
        var DPArr = new Nullable<int>[UB + 1];
        DPArr[0] = 0;

        int MaxSum = 0;

        foreach (ClubInfoDef EachClubInfo in ClubInfoList) {
            for (int I = UB; 0 <= I; I--) {
                if (DPArr[I] == null) continue;

                int NewInd = I + EachClubInfo.Buinsuu;
                if (NewInd > UB) continue;

                int wkSum = DPArr[I].Value + EachClubInfo.Hirosa;

                if (DPArr[NewInd] == null || DPArr[NewInd].Value < wkSum) {
                    DPArr[NewInd] = wkSum;
                    if (MaxSum < wkSum)
                        MaxSum = wkSum;
                }
            }
        }
        Console.WriteLine(MaxSum);
    }
}

実行結果

28800

解説

動的計画法でナイーブに解いてます。