ABC263-D Left Right Operation

問題へのリンク

C#のソース(累積Minを使う方法)

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 4 3");
            WillReturn.Add("5 5 0 6 3");
            //14
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 10 10");
            WillReturn.Add("1 2 3 4");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 -5 -3");
            WillReturn.Add("9 -6 10 -1 2 10 -1 7 -15 5");
            //-58
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long L = wkArr[1];
        long R = wkArr[2];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long UB = AArr.GetUpperBound(0);

        var AnswerKouho = new List<long>();

        // 左からLで変換した時の累積Minを求める
        var RunMinDict = new Dictionary<long, long>();
        long CurrSum = AArr.Sum();
        long CurrMin = CurrSum;
        AnswerKouho.Add(CurrMin);
        RunMinDict[-1] = CurrMin;
        for (long I = 0; I <= UB; I++) {
            CurrSum -= AArr[I];
            CurrSum += L;
            CurrMin = Math.Min(CurrMin, CurrSum);
            RunMinDict[I] = CurrMin;
        }
        AnswerKouho.Add(RunMinDict.Values.Min());

        // 右からRで変換を全て試す
        CurrSum = 0;
        long EarseSum = 0;
        for (long I = UB; 0 <= I; I--) {
            CurrSum += R;
            EarseSum += AArr[I];

            long Kouho = CurrSum + RunMinDict[I - 1] - EarseSum;
            AnswerKouho.Add(Kouho);
        }
        Console.WriteLine(AnswerKouho.Min());
    }
}

C#のソース(耳DPを使う方法)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long L = wkArr[1];
        long R = wkArr[2];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long UB = AArr.GetUpperBound(0);

        // 合計値の最小値[状態] なDP表
        // 状態0 Lを設定
        // 状態1 設定しない
        // 状態2 Rを設定

        // 状態番号が減る遷移は不可とする

        long?[] PrevDP = new long?[2 + 1];
        PrevDP[0] = L;
        PrevDP[1] = AArr[0];
        PrevDP[2] = R;

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

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

                if (J == 0) {
                    UpdateAct(0, PrevDP[J].Value + L);
                    UpdateAct(1, PrevDP[J].Value + AArr[I]);
                    UpdateAct(2, PrevDP[J].Value + R);
                }
                if (J == 1) {
                    UpdateAct(1, PrevDP[J].Value + AArr[I]);
                    UpdateAct(2, PrevDP[J].Value + R);
                }
                if (J == 2) {
                    UpdateAct(2, PrevDP[J].Value + R);
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Min());
    }
}

解説

最初にLでどこまで変換できるかの、累積Minを求めておいてから、
Rでどこまで変換するかを全探索してます。

耳DPで解くこともできます。