典型90問 056 Lucky Bag（★5）

問題へのリンク

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 34");
            WillReturn.Add("3 14");
            WillReturn.Add("15 9");
            WillReturn.Add("26 5");
            //BAB
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 77");
            WillReturn.Add("1 16");
            WillReturn.Add("3 91");
            WillReturn.Add("43 9");
            WillReturn.Add("4 26");
            WillReturn.Add("23 11");
            //BABBA
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 59");
            WillReturn.Add("8 13");
            WillReturn.Add("55 5");
            WillReturn.Add("58 8");
            WillReturn.Add("23 14");
            WillReturn.Add("4 61");
            //Impossible
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

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

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

        SplitAct(InputList[0]);
        int N = wkArr[0];
        int S = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        // 到達可否[日付,合計]なDP表
        bool[,] DPArr = new bool[N + 1, S + 1];
        DPArr[0, 0] = true;

        for (int I = 0; I <= N - 1; I++) {
            for (int J = 0; J <= S; J++) {
                if (DPArr[I, J] == false) continue;

                Action<int, int> UpdateAct = (pNewI, pNewJ) =>
                {
                    if (pNewJ > S) return;

                    DPArr[pNewI, pNewJ] = true;
                };

                int CostA = mABInfoList[I].A;
                int CostB = mABInfoList[I].B;

                int NewI = I + 1;

                UpdateAct(NewI, J + CostA);
                UpdateAct(NewI, J + CostB);
            }
        }

        if (DPArr[N, S] == false) {
            Console.WriteLine("Impossible");
            return;
        }

        // 復元処理
        var AnswerList = new List<char>();
        int CurrJ = S;
        for (int I = N; 1 <= I; I--) {
            Func<int, char, bool> BackAct = (pNewJ, pChar) =>
            {
                if (pNewJ < 0) return false;
                if (DPArr[I - 1, pNewJ] == false) return false;
                CurrJ = pNewJ;
                AnswerList.Add(pChar);
                return true;
            };

            int CostA = mABInfoList[I - 1].A;
            int CostB = mABInfoList[I - 1].B;

            bool Result = BackAct(CurrJ - CostA, 'A');
            if (Result == false) {
                BackAct(CurrJ - CostB, 'B');
            }
        }
        AnswerList.Reverse();
        AnswerList.ForEach(pX => Console.Write(pX));
        Console.WriteLine();
    }
}

解説

到達可否[日付,合計]を更新するDPを行ってから、
ゴールから復元してます。