ABC410-E Battles in a Row

問題へのリンク

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 10 14");
            WillReturn.Add("5 8");
            WillReturn.Add("5 6");
            WillReturn.Add("7 9");
            WillReturn.Add("99 99");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3000 3000");
            WillReturn.Add("3 3");
            WillReturn.Add("3 3");
            WillReturn.Add("3 3");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 8 8");
            WillReturn.Add("2 2");
            WillReturn.Add("2 3");
            WillReturn.Add("2 2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("1 2");
            WillReturn.Add("3 3");
            WillReturn.Add("3 2");
            WillReturn.Add("3 1");
            WillReturn.Add("3 2");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        // 最大MP[HP]
        var PrevDP = new Dictionary<long, long>();
        PrevDP[HP] = MP;

        long Answer = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long NeedHP = wkArr[0];
            long NeedMP = wkArr[1];

            var CurrDP = new Dictionary<long, long>();
            foreach (var EachPair in PrevDP) {
                long CurrHP = EachPair.Key;
                long CurrMP = EachPair.Value;

                Action<long, long> UpsertAct = (pNewHP, pNewMP) =>
                {
                    if (pNewHP < 0) return;
                    if (pNewMP < 0) return;

                    if (CurrDP.ContainsKey(pNewHP)) {
                        if (CurrDP[pNewHP] >= pNewMP) {
                            return;
                        }
                    }
                    CurrDP[pNewHP] = pNewMP;
                };

                UpsertAct(CurrHP - NeedHP, CurrMP);
                UpsertAct(CurrHP, CurrMP - NeedMP);
            }

            PrevDP = CurrDP;
            if (PrevDP.Count > 0) {
                Answer++;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

到達可否[残りHP,残りMP]のBool型のDPだと
計算量は、O(N * HP * MP)となりTLEします。

Bool型のDPは無駄が多いので
最大MP[HP]で状態を持つようにすると
計算量は、O(N * HP)となりACできます。

類題

ABC364-E Maximum Glutton