パ研合宿コンペティション 3日目 D なぎさちゃんの別荘

問題へのリンク

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("70");
            WillReturn.Add("10");
            WillReturn.Add("50");
            WillReturn.Add("20");
            //150
            //80
            //80
            //130
            //150
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            WillReturn.Add("70");
            WillReturn.Add("10");
            WillReturn.Add("-2000");
            WillReturn.Add("10000");
            WillReturn.Add("-2000");
            WillReturn.Add("50");
            WillReturn.Add("20");
            //8080
            //8010
            //8000
            //10000
            //10000
            //8000
            //8050
            //8070
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7");
            WillReturn.Add("-45");
            WillReturn.Add("-45");
            WillReturn.Add("-45");
            WillReturn.Add("-45");
            WillReturn.Add("-45");
            WillReturn.Add("-45");
            //0
            //0
            //0
            //0
            //0
            //0
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mRoomArr;
    static long UB;

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

        var RoomList = new List<long>();
        RoomList.Add(0);
        foreach (string EachStr in InputList.Skip(1)) {
            long CurrC = long.Parse(EachStr);
            RoomList.Add(CurrC);
            RoomList.Add(0);
        }
        mRoomArr = RoomList.ToArray();
        UB = mRoomArr.GetUpperBound(0);

        Dictionary<long, long> ResultDictLeft = ExecDPLeft();
        Dictionary<long, long> ResultDictRight = ExecDPRight();

        for (long I = 0; I <= UB; I++) {
            if (I % 2 == 1) continue;

            var AnswerList = new List<long>();
            AnswerList.Add(0);
            AnswerList.Add(ResultDictLeft[I]);
            AnswerList.Add(ResultDictRight[I]);
            Console.WriteLine(AnswerList.Max());
        }
    }

    // 左端からDP
    static Dictionary<long, long> ExecDPLeft()
    {
        // 累積和の最大値[Ind]なDict
        var ResultDict = new Dictionary<long, long>();
        ResultDict[0] = 0;

        for (long I = 1; I <= UB; I++) {
            long Kouho1 = mRoomArr[I];
            long Kouho2 = ResultDict[I - 1] + mRoomArr[I];
            ResultDict[I] = Math.Max(Kouho1, Kouho2);
        }
        return ResultDict;
    }

    // 右端からDP
    static Dictionary<long, long> ExecDPRight()
    {
        // 累積和の最大値[Ind]なDict
        var ResultDict = new Dictionary<long, long>();
        ResultDict[UB] = 0;

        for (long I = UB - 1; 0 <= I; I--) {
            long Kouho1 = mRoomArr[I];
            long Kouho2 = ResultDict[I + 1] + mRoomArr[I];
            ResultDict[I] = Math.Max(Kouho1, Kouho2);
        }
        return ResultDict;
    }
}

解説

辺とノードがあるとややこしいので、
コスト0のノードを最初に追加してます。

初期処理として、
左端からDPし、累積和の最大値[Ind]なDictを求めてます。
右端からDPし、累積和の最大値[Ind]なDictを求めてます。

後は、定数の処理で解を求めることができます。