ABC232-F Simple Operations on Sequence

問題へのリンク

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("4 3 5");
            WillReturn.Add("4 2 5 2");
            WillReturn.Add("6 4 2 1");
            //16
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 12345 6789");
            WillReturn.Add("1 2 3 4 5");
            WillReturn.Add("1 2 3 4 5");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("18 20719114 5117250357733867");
            WillReturn.Add("10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712");
            WillReturn.Add("14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077");
            //13104119429316474
        }
        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 N = wkArr[0];
        long X = wkArr[1];
        long Y = wkArr[2];

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

        long AllBitOn = (1 << (int)N) - 1;

        // 最小コスト[使用済BitSet]なDP表
        long?[] DPArr = new long?[AllBitOn + 1];
        DPArr[0] = 0;

        for (long I = 1; I <= N; I++) { // 移動回数でループ
            for (long J = AllBitOn; 0 <= J; J--) { // 遷移元でループ
                if (DPArr[J].HasValue == false) continue;

                for (long K = 0; K <= N - 1; K++) { // 移動元
                    long CurrBit = (1 << (int)K);
                    if ((J & CurrBit) > 0) continue; // 再使用は不可

                    // 転倒数を、使用済BitSetから求める
                    long TentouCnt = 0;
                    long CheckBit = CurrBit;
                    while (CheckBit > 0) {
                        CheckBit /= 2;
                        if ((J & CheckBit) > 0) TentouCnt++;
                    }

                    long NewCost = DPArr[J].Value;
                    NewCost += TentouCnt * Y;

                    long Diff = Math.Abs(AArr[AArr.GetUpperBound(0) - K] - BArr[I - 1]);
                    NewCost += Diff * X;

                    long NewJ = J | CurrBit;
                    if (DPArr[NewJ].HasValue) {
                        if (DPArr[NewJ].Value <= NewCost) {
                            continue;
                        }
                    }
                    DPArr[NewJ] = NewCost;
                }
            }
        }
        Console.WriteLine(DPArr[AllBitOn]);
    }
}

解説

転倒数を求めつつ、BitDPで解いてます。