第17回PAST H 履修登録

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 4");
            WillReturn.Add("3 1 2");
            WillReturn.Add("4 1 2");
            WillReturn.Add("5 2 2");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 100");
            WillReturn.Add("1 100 1");
            WillReturn.Add("1 200 1");
            WillReturn.Add("1 300 1");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 100");
            WillReturn.Add("10 5 99");
            WillReturn.Add("10 5 99");
            //-1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 522");
            WillReturn.Add("4575 1426 4445");
            WillReturn.Add("3772 81 3447");
            WillReturn.Add("629 3497 2202");
            WillReturn.Add("2775 4325 3982");
            WillReturn.Add("4784 3417 2156");
            WillReturn.Add("1932 902 728");
            WillReturn.Add("3537 3857 739");
            WillReturn.Add("1918 4211 4679");
            WillReturn.Add("3506 3340 1568");
            WillReturn.Add("1868 16 2940");
            //629
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct SubjectDef
    {
        internal long Cost;
        internal long No;
        internal long Tani;
    }
    static List<SubjectDef> mSubjectList = new List<SubjectDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long NeedTaniSum = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            SubjectDef WillAdd;
            WillAdd.Cost = wkArr[0];
            WillAdd.No = wkArr[1];
            WillAdd.Tani = wkArr[2];
            mSubjectList.Add(WillAdd);
        }

        // Noの昇順でソート
        mSubjectList = mSubjectList.OrderBy(pX => pX.No).ToList();

        // 最小コスト[合計単位]なDP表
        var PrevDP = new Dictionary<long, long>();
        PrevDP[0] = 0;

        Dictionary<long, long> CurrDP = new Dictionary<long, long>();

        var AnswerList = new List<long>();
        long UB = mSubjectList.Count - 1;
        for (int I = 0; I <= UB; I++) {
            foreach (var EachPair in PrevDP) {
                long NewKey = EachPair.Key + mSubjectList[I].Tani;
                long NewVal = EachPair.Value + mSubjectList[I].Cost;

                if (NewKey >= NeedTaniSum) {
                    AnswerList.Add(NewVal);
                    continue;
                }

                if (CurrDP.ContainsKey(NewKey)) {
                    if (CurrDP[NewKey] <= NewVal) {
                        continue;
                    }
                }
                CurrDP[NewKey] = NewVal;
            }

            bool IsLastGroup = false;
            if (I == UB) IsLastGroup = true;
            if (I < UB && mSubjectList[I].No != mSubjectList[I + 1].No) {
                IsLastGroup = true;
            }

            if (IsLastGroup) {
                PrevDP = CurrDP;
                PrevDP[0] = 0;
                CurrDP = new Dictionary<long, long>(PrevDP);
            }
        }

        if (AnswerList.Count > 0) {
            Console.WriteLine(AnswerList.Min());
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

解説

合計単位をキーに持てば状態数が5000で済むので
合計単位をキーに持って、
最小コスト[合計単位]なDP表を更新してます。

同じ授業は1つしか受講できない、特殊な01ナップサック問題なので、
最初にNoの昇順にソートしてます。