TDP L 猫

問題へのリンク

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

    static int[,] mScoreArr;
    static int[,] mBanArr;
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mScoreArr = CreateBanArr(InputList.Skip(1));

        UB = mScoreArr.GetUpperBound(0);

        // 得られるスコア [猫 , 何匹の猫と接続するか ] な2次元配列
        mBanArr = new int[UB + 1, UB + 1];
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 1; LoopY <= LoopX; LoopY++) {
                mBanArr[LoopX, LoopY] = mScoreArr[LoopX, LoopX - LoopY];
                mBanArr[LoopX, LoopY] += mBanArr[LoopX, LoopY - 1];
            }
        }

        // 最大スコア [ 最後の猫が何匹の猫と接続したか ] なDP表
        int?[] PrevDP = new int?[1];
        PrevDP[0] = 0;

        int Answer = int.MinValue;
        for (int LoopX = 0; LoopX <= UB - 1; LoopX++) {
            int MaxVal = int.MinValue;
            int?[] CurrDP = new int?[LoopX + 2];
            for (int LoopY = LoopX; 0 <= LoopY; LoopY--) {
                if (PrevDP[LoopY].HasValue == false) continue;
                if (MaxVal >= PrevDP[LoopY]) {
                    continue;
                }
                MaxVal = PrevDP[LoopY].Value;
                for (int I = 0; I <= LoopY + 1; I++) {
                    int NewVal = PrevDP[LoopY].Value + mBanArr[LoopX + 1, I];
                    if (CurrDP[I].HasValue) {
                        if (CurrDP[I].Value >= NewVal) {
                            continue;
                        }
                    }
                    CurrDP[I] = NewVal;
                    Answer = Math.Max(Answer, NewVal);
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(Answer * 2);
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

        int[] IntArr = { };
        Action<string> SplitAct = pStr =>
            IntArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

 0 -3  5  2 -6
-3  0  6 -3  1
 5  6  0  2  0
 2 -3  2  0  4
-6  1  0  4  0

上記の入力データで
得られるスコア [猫 , 何匹の猫と接続するか ] な2次元配列は下記になります。
    0  1  2  3  4
 0  0  0  0  0  0
 1    -3  6  2  4
 2       11 -1  4
 3           1  5
 4             -1

遷移を考えると
[0,0]から開始して、
X座標は1増える、
Y座標は、(0から元のY座標+1) のいずれか
に遷移できます。

このグラフで、[0,0]から右端までの各経路での
(配列値の合計の最大値)*2が解になります。
DFSするとTLEになるので、DPでこの値を求めてます。