ABC275-F Erase Subarrays

問題へのリンク

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

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

        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        // 最小コスト[残す数値のSum,削除区間が連続中か？]なDP表
        int?[,] PrevDP = new int?[M + 1, 2];
        PrevDP[0, 0] = 0;

        foreach (int EachA in AArr) {
            int?[,] CurrDP = new int?[M + 1, 2];
            for (int I = 0; I <= M; I++) {
                for (int J = 0; J <= 1; J++) {
                    if (PrevDP[I, J].HasValue == false) continue;

                    Action<int, int, int> UpdateAct = (pNewI, pNewJ, pCost) =>
                    {
                        if (pNewI > M) return;

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

                    // 数値を削除する場合
                    if (J == 1) {
                        UpdateAct(I, 1, PrevDP[I, J].Value);
                    }
                    else {
                        UpdateAct(I, 1, PrevDP[I, J].Value + 1);
                    }

                    // 数値を削除しない場合
                    UpdateAct(I + EachA, 0, PrevDP[I, J].Value);
                }
            }
            PrevDP = CurrDP;
        }

        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= M; I++) {
            var AnswerKouho = new List<int>();

            if (PrevDP[I, 0].HasValue) AnswerKouho.Add(PrevDP[I, 0].Value);
            if (PrevDP[I, 1].HasValue) AnswerKouho.Add(PrevDP[I, 1].Value);

            if (AnswerKouho.Count > 0) {
                sb.Append(AnswerKouho.Min());
            }
            else {
                sb.Append(-1);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

解説

最小コスト[残す数値のSum,削除区間が連続中か？]
を更新するDPで解いてます。