ABC466-E Range Flip

問題へのリンク

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("7 2");
            WillReturn.Add("2 1");
            WillReturn.Add("6 9");
            WillReturn.Add("3 5");
            WillReturn.Add("9 2");
            WillReturn.Add("4 8");
            WillReturn.Add("7 4");
            WillReturn.Add("5 6");
            //45
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 6");
            WillReturn.Add("9 6");
            WillReturn.Add("3 2");
            WillReturn.Add("8 1");
            WillReturn.Add("7 5");
            WillReturn.Add("8 4");
            //35
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 1");
            WillReturn.Add("2 7");
            WillReturn.Add("9 4");
            WillReturn.Add("1 1");
            WillReturn.Add("6 1");
            WillReturn.Add("3 4");
            WillReturn.Add("8 9");
            WillReturn.Add("1 2");
            WillReturn.Add("7 5");
            WillReturn.Add("3 9");
            //47
        }
        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();
    }

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long K = wkArr[1];

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

        // スコア[裏返し中 . 裏返し回数]なDP表
        long?[,] PrevDP = new long?[2, K + 1];
        PrevDP[0, 0] = 0;

        foreach (ABInfoDef EachABInfo in mABInfoList) {
            long?[,] CurrDP = new long?[2, K + 1];
            for (long I = 0; I <= 1; I++) {
                for (long J = 0; J <= K; J++) {
                    if (PrevDP[I, J].HasValue == false) continue;

                    Action<long> UpdateAct = (pNewI) =>
                    {
                        long NewJ = J;
                        if (I == 0 && pNewI == 1) {
                            NewJ++;
                        }
                        if (NewJ > K) return;

                        long NewVal = PrevDP[I, J].Value;
                        if (pNewI == 0) {
                            NewVal += EachABInfo.A;
                        }
                        else {
                            NewVal += EachABInfo.B;
                        }

                        if (CurrDP[pNewI, NewJ].HasValue) {
                            if (CurrDP[pNewI, NewJ] >= NewVal) {
                                return;
                            }
                        }
                        CurrDP[pNewI, NewJ] = NewVal;
                    };

                    UpdateAct(0);
                    UpdateAct(1);
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = long.MinValue;
        for (long I = 0; I <= 1; I++) {
            for (long J = 0; J <= K; J++) {
                if (PrevDP[I, J].HasValue) {
                    Answer = Math.Max(Answer, PrevDP[I, J].Value);
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

スコア[裏返し中 . 裏返し回数]なDP表を更新してます。