ABC229-F Make Bipartite

問題へのリンク

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

    static long mN;
    static long UB;
    static long[] mAArr;
    static long[] mBArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = long.Parse(InputList[0]);
        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mBArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mN;

        long Result = Solve();
        Console.WriteLine(Result);
    }

    // DPして、解を返す
    static long Solve()
    {
        // 最小コスト[現在ノード , 現在ノードの色 , ノード1の色]なDP表
        long?[, ,] DPArr = new long?[UB + 1, 2, 2];
        DPArr[1, 0, 0] = 0;
        DPArr[1, 1, 1] = mAArr[0];

        // 配るDP
        for (long I = 1; I <= UB; I++) {
            long NewI = I + 1;
            if (NewI > UB) continue;

            for (long J = 0; J <= 1; J++) {
                for (long K = 0; K <= 1; K++) {

                    if (DPArr[I, J, K].HasValue == false) continue;

                    // 塗る色と、コストを引数として、DP表を更新
                    Action<long, long> UpdateAct = (pColor, pCost) =>
                    {
                        if (DPArr[NewI, pColor, K].HasValue) {
                            if (DPArr[NewI, pColor, K].Value <= pCost) {
                                return;
                            }
                        }
                        DPArr[NewI, pColor, K] = pCost;
                    };

                    // 白く塗る場合
                    long CurrCost1 = DPArr[I, J, K].Value;
                    if (J == 0) {
                        CurrCost1 += mBArr[I - 1];
                    }
                    if (NewI == UB && K == 0) {
                        CurrCost1 += mBArr.Last();
                    }
                    UpdateAct(0, CurrCost1);

                    // 黒く塗る場合
                    long CurrCost2 = DPArr[I, J, K].Value + mAArr[I];
                    if (J == 1) {
                        CurrCost2 += mBArr[I - 1];
                    }
                    if (NewI == UB && K == 1) {
                        CurrCost2 += mBArr.Last();
                    }
                    UpdateAct(1, CurrCost2);
                }
            }
        }

        var AnswerKouho = new List<long>();
        for (long J = 0; J <= 1; J++) {
            for (long K = 0; K <= 1; K++) {
                if (DPArr[UB, J, K].HasValue) {
                    AnswerKouho.Add(DPArr[UB, J, K].Value);
                }
            }
        }
        return AnswerKouho.Min();
    }
}

解説

中心ノードは、必ず黒色として、
各ノードを白か黒で塗る、DPで解いてます。