AOJ 0777 白色光 2 (White Light 2)

問題へのリンク

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("6");
            WillReturn.Add("GRBBRG");
            WillReturn.Add("3 4 5");
            //16
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("BRG");
            WillReturn.Add("1000000000 1000000000 1");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("GRB");
            WillReturn.Add("9 11 14");
            //27
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("9");
            WillReturn.Add("RGBRGBRGB");
            WillReturn.Add("1000000000 1000000000 1");
            //0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("20");
            WillReturn.Add("BRGBRGBBGBBBGRRBBBRB");
            WillReturn.Add("1000000000 1000000000 1");
            //2000000008
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("23");
            WillReturn.Add("BBGRGBBBBBBGRRGGGGBGGGG");
            WillReturn.Add("786820955 792349124 710671229");
            //10107224827
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

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

        char[] SArr = InputList[1].ToCharArray();
        long UB = SArr.GetUpperBound(0);

        long[] wkArr = GetSplitArr(InputList[2]);
        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];

        // 次の文字がRなら、状態番号は0
        // 次の文字がGなら、状態番号は1
        // 次の文字がBなら、状態番号は2

        // 最小コスト[状態番号,左を消せるか?]なDP表
        long?[,] PrevDP = new long?[3 + 1, 1 + 1];
        PrevDP[0, 1] = 0;

        var AnswerList = new List<long>();

        for (long I = 0; I <= UB; I++) {
            long?[,] CurrDP = new long?[3 + 1, 1 + 1];

            for (long J = 0; J <= 2; J++) {
                for (long K = 0; K <= 1; K++) {
                    if (PrevDP[J, K].HasValue == false) continue;

                    Action<long, long, long> UpdateAct = (pNewJ, pNewK, pNewVal) =>
                    {
                        if (CurrDP[pNewJ, pNewK].HasValue) {
                            if (CurrDP[pNewJ, pNewK].Value <= pNewVal) {
                                return;
                            }
                        }
                        CurrDP[pNewJ, pNewK] = pNewVal;
                    };

                    // 消す遷移
                    if (K == 1) {
                        UpdateAct(J, K, PrevDP[J, K].Value + A);
                    }

                    if (SArr[I] == 'R' && J == 0
                     || SArr[I] == 'G' && J == 1
                     || SArr[I] == 'B' && J == 2) {
                        // そのまま使う遷移
                        UpdateAct((J + 1) % 3, 0, PrevDP[J, K].Value);
                    }
                    else {
                        // 変更する遷移
                        UpdateAct((J + 1) % 3, 0, PrevDP[J, K].Value + C);
                    }

                    // 右を全て消す遷移
                    if (J == 0) {
                        AnswerList.Add(PrevDP[J, K].Value + B * (UB - I + 1));
                    }
                }
            }
            PrevDP = CurrDP;
        }

        if (PrevDP[0, 0].HasValue) {
            AnswerList.Add(PrevDP[0, 0].Value);
        }
        if (PrevDP[0, 1].HasValue) {
            AnswerList.Add(PrevDP[0, 1].Value);
        }
        Console.WriteLine(AnswerList.Min());
    }
}

解説

最小コスト[状態番号,左を消せるか?]でDPしてます。