ABC322-E Product Development

問題へのリンク

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("4 3 5");
            WillReturn.Add("5 3 0 2");
            WillReturn.Add("3 1 2 3");
            WillReturn.Add("3 2 4 0");
            WillReturn.Add("1 0 1 4");
            //9
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 3 5");
            WillReturn.Add("85 1 0 1");
            WillReturn.Add("37 1 1 0");
            WillReturn.Add("38 2 0 0");
            WillReturn.Add("45 0 2 2");
            WillReturn.Add("67 1 1 0");
            WillReturn.Add("12 2 2 0");
            WillReturn.Add("94 2 2 1");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ItemDef
    {
        internal long Cost;
        internal long Add1;
        internal long Add2;
        internal long Add3;
        internal long Add4;
        internal long Add5;
    }
    static List<ItemDef> mItemList = new List<ItemDef>();

    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 K = wkArr[1];
        long P = wkArr[2];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ItemDef WillAdd;
            WillAdd.Cost = wkArr[0];
            WillAdd.Add1 = WillAdd.Add2 = WillAdd.Add3 = WillAdd.Add4 = WillAdd.Add5 = 0;

            if (K >= 1) WillAdd.Add1 = wkArr[1];
            if (K >= 2) WillAdd.Add2 = wkArr[2];
            if (K >= 3) WillAdd.Add3 = wkArr[3];
            if (K >= 4) WillAdd.Add4 = wkArr[4];
            if (K >= 5) WillAdd.Add5 = wkArr[5];
            mItemList.Add(WillAdd);
        }

        // 最小コスト[状態]なDP表
        var PrevDP = new Dictionary<long, long>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.P1 = FirstJyoutai.P2 = FirstJyoutai.P3 = FirstJyoutai.P4 = FirstJyoutai.P5 = 0;
        long Hash = GetHash(FirstJyoutai);
        PrevDP[Hash] = 0;

        foreach (ItemDef EachItemInfo in mItemList) {
            var CurrDP = new Dictionary<long, long>(PrevDP);
            foreach (var EachPair in PrevDP) {
                JyoutaiDef NextJyoutai = GetJyoutai(EachPair.Key);
                long NewCost = EachPair.Value + EachItemInfo.Cost;

                NextJyoutai.P1 += EachItemInfo.Add1;
                NextJyoutai.P2 += EachItemInfo.Add2;
                NextJyoutai.P3 += EachItemInfo.Add3;
                NextJyoutai.P4 += EachItemInfo.Add4;
                NextJyoutai.P5 += EachItemInfo.Add5;

                NextJyoutai.P1 = Math.Min(P, NextJyoutai.P1);
                NextJyoutai.P2 = Math.Min(P, NextJyoutai.P2);
                NextJyoutai.P3 = Math.Min(P, NextJyoutai.P3);
                NextJyoutai.P4 = Math.Min(P, NextJyoutai.P4);
                NextJyoutai.P5 = Math.Min(P, NextJyoutai.P5);

                long NextHash = GetHash(NextJyoutai);

                if (CurrDP.ContainsKey(NextHash)) {
                    if (CurrDP[NextHash] <= NewCost) {
                        continue;
                    }
                }
                CurrDP[NextHash] = NewCost;
            }
            PrevDP = CurrDP;
        }

        var AnswerKouho = new List<long>();
        foreach (var EachPair in PrevDP) {
            JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);
            if (K >= 1 && CurrJyoutai.P1 < P) continue;
            if (K >= 2 && CurrJyoutai.P2 < P) continue;
            if (K >= 3 && CurrJyoutai.P3 < P) continue;
            if (K >= 4 && CurrJyoutai.P4 < P) continue;
            if (K >= 5 && CurrJyoutai.P5 < P) continue;

            AnswerKouho.Add(EachPair.Value);
        }

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

    struct JyoutaiDef
    {
        internal long P1;
        internal long P2;
        internal long P3;
        internal long P4;
        internal long P5;
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long WillReturn = 0;
        WillReturn += pJyoutai.P5;
        WillReturn += pJyoutai.P4 * 10;
        WillReturn += pJyoutai.P3 * 100;
        WillReturn += pJyoutai.P2 * 1000;
        WillReturn += pJyoutai.P1 * 10000;
        return WillReturn;
    }

    static JyoutaiDef GetJyoutai(long pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.P5 = pHash % 10; pHash /= 10;
        WillReturn.P4 = pHash % 10; pHash /= 10;
        WillReturn.P3 = pHash % 10; pHash /= 10;
        WillReturn.P2 = pHash % 10; pHash /= 10;
        WillReturn.P1 = pHash % 10; pHash /= 10;
        return WillReturn;
    }
}

解説

最小コスト[状態]でDPしてます。