AOJ本の読書メモ   AOJ    次のAOJの問題へ    前のAOJの問題へ

AOJ 0722 飴 2 (Candies 2)


問題へのリンク


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 4");
            WillReturn.Add("1 3 2 4 3");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3");
            WillReturn.Add("3 7 1 5 6 4");
            //21
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 2");
            WillReturn.Add("3 3 2 2 1");
            //11
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("12 5");
            WillReturn.Add("864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728");
            //4427122428
        }
        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 K = wkArr[1];

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

        long Result = Solve(K, AArr.ToArray());
        Console.WriteLine(Result);
    }

    static long Solve(long pK, long[] pAArr)
    {
        long Answer = 0;
        long UB = pAArr.GetUpperBound(0);

        // 最大スコア[1つ前の飴 , 2つ前の飴]
        long[,] ScoreArr = new long[UB + 1, UB + 1];

        // 飴を2個取る組み合わせを全列挙
        for (long I = 0; I <= UB; I++) {
            for (long J = 0; J <= I - 1; J++) {
                long SumVal = pAArr[I] + pAArr[J];
                ScoreArr[I, J] = SumVal;
                Answer = Math.Max(Answer, SumVal);
            }
        }

        // 最大値情報[1つ前の飴]
        var SegTreeMaxInfoDict = new Dictionary<long, MaxInfoDef>();
        for (long I = 0; I <= UB; I++) {
            SegTreeMaxInfoDict[I] = new MaxInfoDef();
            SegTreeMaxInfoDict[I].CurrInd = 0;
            SegTreeMaxInfoDict[I].RunMax = 0;
        }

        // 3個目以降の飴を取る場合を全探索
        for (long I = pK; I <= UB; I++) {
            for (long J = I - 1; 1 <= J; J--) {
                long RangeSta = 0;
                long RangeEnd = Math.Min(J - 1, I - pK);
                // 1点更新区間最大値のセグ木の更新
                if (RangeSta <= RangeEnd) {
                    while (true) {
                        long CurrInd = SegTreeMaxInfoDict[J].CurrInd;
                        long RunMax = SegTreeMaxInfoDict[J].RunMax;
                        RunMax = Math.Max(RunMax, ScoreArr[J, CurrInd]);

                        SegTreeMaxInfoDict[J].RunMax = RunMax;
                        if (CurrInd < RangeEnd) {
                            CurrInd++;
                            SegTreeMaxInfoDict[J].CurrInd = CurrInd;
                        }
                        else {
                            break;
                        }
                    }

                    long GainVal = SegTreeMaxInfoDict[J].RunMax;
                    GainVal = Math.Max(GainVal, ScoreArr[J, RangeEnd]);
                    long NewVal = GainVal + pAArr[I];

                    ScoreArr[I, J] = Math.Max(ScoreArr[I, J], NewVal);
                    Answer = Math.Max(Answer, NewVal);
                }
            }
        }

        return Answer;
    }

    // 1点更新区間最大値のセグ木の更新待ちキューの構造体
    class MaxInfoDef
    {
        internal long CurrInd;
        internal long RunMax;
    }
}


解説

1点更新区間最大値を取得なセグ木が存在すると
仮定して、セグ木の区間最大値を管理してます。