ARC137-B Count 1's

問題へのリンク

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

    static int UB;

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

        int MaxOneCnt = ExecDP(AArr);

        var ChangeList = new List<int>();
        foreach (int EachA in AArr) {
            if (EachA == 0) ChangeList.Add(1);
            if (EachA == 1) ChangeList.Add(0);
        }
        int MaxZeroCnt = ExecDP(ChangeList.ToArray());
        int MinOneCnt = AArr.Length - MaxZeroCnt;

        Console.WriteLine(MaxOneCnt - MinOneCnt + 1);
    }

    // 1を最大で何個にできるかを返す
    static int ExecDP(int[] pAArr)
    {
        int DefaultCnt = pAArr.Count(pX => pX == 1);

        // 最大スコア[区間End] なDP表
        int[] DPArr = new int[UB + 1];

        for (int I = 0; I <= UB; I++) {
            // 貰うDP

            var KouhoList = new List<int>();
            if (pAArr[I] == 0) {
                KouhoList.Add(1);
            }
            else {
                KouhoList.Add(-1);
            }

            int PrevInd = I - 1;
            if (PrevInd >= 0) {
                if (pAArr[I] == 0) {
                    KouhoList.Add(DPArr[I - 1] + 1);
                }
                else {
                    KouhoList.Add(DPArr[I - 1] - 1);
                }
            }

            DPArr[I] = KouhoList.Max();
        }

        return Math.Max(DefaultCnt, DefaultCnt + DPArr.Max());
    }
}

解説

PPPMMPPPMMMMMMMPPPPMM
という文字列でPの数が、基準スコアとし、
自由に区間を選んで
Pは1点、Mは-1点として
スコアを変化させれる時の、最大スコアは、

最大スコア[区間End]
を貰うDPで更新して、求めることができます。

そして、スコアは1点刻みで変化するので
最低スコアから最大スコアまでの、スコアは、全て達成可能です。