B21 Longest Subpalindrome

問題へのリンク

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("11");
            WillReturn.Add("programming");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7");
            WillReturn.Add("abcdcba");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static string mS;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mS = InputList[1];

        int Answer = rec(0, mS.Length - 1);
        Console.WriteLine(Answer);
    }

    // 戻り値 何回マッチできるか
    // 引数1 左端Ind
    // 引数2 右端Ind
    static Dictionary<string, int> mMemo = new Dictionary<string, int>();
    static int rec(int pL, int pR)
    {
        string Hash = string.Format("{0},{1}", pL, pR);
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        if (pL > pR) return 0;

        // 一致したら、回文として使う
        if (mS[pL] == mS[pR]) {
            if (pL < pR) {
                return mMemo[Hash] = 2 + rec(pL + 1, pR - 1);
            }
            else {
                return 1;
            }
        }

        var SeniList = new List<int>();
        SeniList.Add(rec(pL + 1, pR)); // 左端を進める
        SeniList.Add(rec(pL, pR - 1)); // 右端を進める

        return mMemo[Hash] = SeniList.Max();
    }
}

解説

メモ化再帰で解いてます。

Nが1000以下なので、
左端と右端のペアは、1000 Choose 2 で 1000*999 / 2 = 500*999 です。

遷移も3通りしかないので、
メモ化再帰で、間に合います。