ABC251-E Tahakashi and Animals

問題へのリンク

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("2 5 3 2 5");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            WillReturn.Add("29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62");
            //426
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        // 最小コスト[現在ノード , 現在ノードの配布有無 , ノード0の配布有無]なDP表
        long?[, ,] DPArr = new long?[UB + 1, 2, 2];
        DPArr[0, 0, 0] = 0;
        DPArr[0, 1, 1] = AArr[0];

        // 配るDP
        for (long I = 0; I <= UB - 1; I++) {
            long NewI = I + 1;
            if (NewI > UB) continue;

            for (long J = 0; J <= 1; J++) {
                for (long K = 0; K <= 1; K++) {

                    if (DPArr[I, J, K].HasValue == false) continue;

                    // 配布有無と、コストを引数として、DP表を更新
                    Action<long, long> UpdateAct = (pNewJ, pCost) =>
                    {
                        if (DPArr[NewI, pNewJ, K].HasValue) {
                            if (DPArr[NewI, pNewJ, K].Value <= pCost) {
                                return;
                            }
                        }
                        DPArr[NewI, pNewJ, K] = pCost;
                    };

                    // 配布する場合
                    long CurrCost1 = DPArr[I, J, K].Value + AArr[I + 1];
                    UpdateAct(1, CurrCost1);

                    // 配布しない場合
                    bool NeedSend = false;
                    if (J == 0) NeedSend = true;
                    if (NewI == UB && K == 0) {
                        NeedSend = true;
                    }
                    if (NeedSend == false) {
                        long CurrCost2 = DPArr[I, J, K].Value;
                        UpdateAct(0, CurrCost2);
                    }
                }
            }
        }

        var AnswerKouho = new List<long>();
        for (long J = 0; J <= 1; J++) {
            for (long K = 0; K <= 1; K++) {
                if (DPArr[UB, J, K].HasValue) {
                    AnswerKouho.Add(DPArr[UB, J, K].Value);
                }
            }
        }
        Console.WriteLine(AnswerKouho.Min());
    }
}

解説

円環で、2ノード連続で、配布しないノードがあってはいけないことをふまえて、
円環で、先頭と直前を状態に持つDPで解いてます。