ABC346-D Gomamayo Sequence

問題へのリンク

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("5");
            WillReturn.Add("00011");
            WillReturn.Add("3 9 2 6 4");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1001");
            WillReturn.Add("1 2 3 4");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("11111100111");
            WillReturn.Add("512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427");
            //2286846953
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] SCharArr = InputList[1].ToCharArray();
        long[] CostArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long UB = CostArr.GetUpperBound(0);

        // 最小コスト[一致数,前の文字]なDP表
        long?[,] PrevDP = new long?[2, 3];
        PrevDP[0, 2] = 0;

        long[] SLongArr = new long[UB + 1];
        for (long I = 0; I <= UB; I++) {
            if (SCharArr[I] == '0') SLongArr[I] = 0;
            if (SCharArr[I] == '1') SLongArr[I] = 1;
        }

        for (long I = 0; I <= UB; I++) {
            long?[,] CurrDP = new long?[2, 3];
            for (long J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    if (PrevDP[J, K].HasValue == false) continue;

                    Action<long, long, long> UpdateAct = (pNewJ, pNewK, pNewCost) =>
                    {
                        if (pNewJ >= 2) return;

                        if (CurrDP[pNewJ, pNewK].HasValue) {
                            if (CurrDP[pNewJ, pNewK].Value <= pNewCost) {
                                return;
                            }
                        }
                        CurrDP[pNewJ, pNewK] = pNewCost;
                    };

                    // 変換する場合
                    long NewJ = J;
                    long NewK = DeriveChangeVal(SLongArr[I]);
                    long NewCost = PrevDP[J, K].Value + CostArr[I];
                    if (K == NewK) {
                        NewJ++;
                    }
                    UpdateAct(NewJ, NewK, NewCost);

                    // 変換しない場合
                    NewJ = J;
                    NewK = SLongArr[I];
                    NewCost = PrevDP[J, K].Value;
                    if (K == NewK) {
                        NewJ++;
                    }
                    UpdateAct(NewJ, NewK, NewCost);
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = long.MaxValue;
        for (long K = 0; K <= PrevDP.GetUpperBound(1); K++) {
            if (PrevDP[1, K].HasValue == false) continue;
            Answer = Math.Min(Answer, PrevDP[1, K].Value);
        }
        Console.WriteLine(Answer);
    }

    static long DeriveChangeVal(long pVal)
    {
        if (pVal == 0) return 1;
        return 0;
    }
}

解説

最小コスト[一致数,前の文字]でDPしてます。
文字は0と1の2通りですが、
初期文字として、2という番兵のような文字を使ってます。