AOJ 0550 お菓子の分割

問題へのリンク

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("6");
            WillReturn.Add("1");
            WillReturn.Add("8");
            WillReturn.Add("12");
            WillReturn.Add("6");
            WillReturn.Add("2");
            //7
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long TotalMasuCnt = long.Parse(InputList[0]);
        long[] CostArr = InputList.Skip(1).Select(pX => long.Parse(pX)).ToArray();

        long UB0 = TotalMasuCnt / 2;
        long UB1 = 1;

        // 最小コスト[Aの取得マス,次にAが取得か？]なDP表
        long?[,] PrevDP = new long?[UB0 + 1, UB1 + 1];
        PrevDP[0, 1] = 0;

        var AnswerList = new List<long>();
        for (long I = 0; I <= CostArr.GetUpperBound(0); I++) {
            long CurrCutCost = CostArr[I];
            long?[,] CurrDP = new long?[UB0 + 1, UB1 + 1];
            for (long J = 0; J <= UB0; J++) {
                for (long K = 0; K <= UB1; K++) {
                    if (PrevDP[J, K].HasValue == false) continue;

                    Action<long, long, long> UpdateAct = (pNewJ, pNewK, pNewVal) =>
                    {
                        long CurrMasuCnt = I + 1;
                        long ACnt = pNewJ;
                        long BCnt = CurrMasuCnt - ACnt;

                        if (ACnt > TotalMasuCnt / 2) return;
                        if (BCnt > TotalMasuCnt / 2) return;

                        if (ACnt == TotalMasuCnt / 2 && pNewK == 0) {
                            AnswerList.Add(pNewVal);
                            return;
                        }
                        if (BCnt == TotalMasuCnt / 2 && pNewK == 1) {
                            AnswerList.Add(pNewVal);
                            return;
                        }

                        if (CurrDP[pNewJ, pNewK].HasValue) {
                            if (CurrDP[pNewJ, pNewK] <= pNewVal) {
                                return;
                            }
                        }
                        CurrDP[pNewJ, pNewK] = pNewVal;
                    };

                    if (K == 0) {
                        // Aが取得に切り替える場合
                        UpdateAct(J, 1, PrevDP[J, K].Value + CurrCutCost);

                        // そのままBが取得する場合
                        UpdateAct(J, 0, PrevDP[J, K].Value);
                    }
                    else {
                        // Bが取得に切り替える場合
                        UpdateAct(J + 1, 0, PrevDP[J, K].Value + CurrCutCost);

                        // そのままAが取得する場合
                        UpdateAct(J + 1, 1, PrevDP[J, K].Value);
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(AnswerList.Min());
    }
}

解説

コストを払えば、AとBのどっちがマスを取得するかを切替できると考え、
最小コスト[Aの取得マス,次にAが取得か？]なDP表を更新してます。