ABC344-D String Bags

問題へのリンク

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("abcde");
            WillReturn.Add("3");
            WillReturn.Add("3 ab abc abcd");
            WillReturn.Add("4 f c cd bcde");
            WillReturn.Add("2 e de");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("abcde");
            WillReturn.Add("3");
            WillReturn.Add("2 ab abc");
            WillReturn.Add("3 f c bcde");
            WillReturn.Add("1 e");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("aaabbbbcccc");
            WillReturn.Add("6");
            WillReturn.Add("2 aa aaa");
            WillReturn.Add("2 dd ddd");
            WillReturn.Add("2 ab aabb");
            WillReturn.Add("4 bbaa bbbc bbb bbcc");
            WillReturn.Add("2 cc bcc");
            WillReturn.Add("3 ccc cccc ccccc");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        string GoalStr = InputList[0];

        var AList = new List<string[]>();
        for (int I = 2; I <= InputList.Count - 1; I++) {
            string[] SplitArr = InputList[I].Split(' ').Skip(1).ToArray();
            SplitArr = SplitArr.OrderBy(pX => pX.Length).ToArray();
            AList.Add(SplitArr);
        }

        // 最小コスト[現在の文字列]
        var PrevDP = new Dictionary<string, long>();
        PrevDP[""] = 0;

        foreach (string[] EachAArr in AList) {
            var CurrDP = new Dictionary<string, long>(PrevDP);
            foreach (var EachPair in PrevDP) {
                foreach (string EachA in EachAArr) {
                    string NewKey = EachPair.Key + EachA;
                    long NewVal = EachPair.Value + 1;

                    if (GoalStr.Length < NewKey.Length) {
                        break;
                    }
                    if (GoalStr.StartsWith(NewKey) == false) {
                        continue;
                    }
                    if (CurrDP.ContainsKey(NewKey)) {
                        if (CurrDP[NewKey] <= NewVal) {
                            continue;
                        }
                    }
                    CurrDP[NewKey] = NewVal;
                }
            }
            PrevDP = CurrDP;
        }

        if (PrevDP.ContainsKey(GoalStr)) {
            Console.WriteLine(PrevDP[GoalStr]);
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

解説

最小コスト[現在の文字列]でDPしてます。
Lengthオーバーでの枝切りと
StartsWithメソッドでの枝切りもしてます。