第7回PAST H 折れ線グラフ

問題へのリンク

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

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int SumVal = AArr.Sum();

        int UB = SumVal;

        // 最小コスト[現在のY座標 , 残りのAVal] なDP表
        double?[,] PrevDP = new double?[UB + 1, UB + 1];
        PrevDP[0, SumVal] = 0;

        for (int LoopX = 1; LoopX <= AArr.GetUpperBound(0); LoopX++) {
            double?[,] CurrDP = new double?[UB + 1, UB + 1];
            for (int I = 0; I <= UB; I++) {
                for (int J = 0; J <= UB; J++) {
                    if (PrevDP[I, J].HasValue == false) continue;

                    for (int K = 0; K <= J; K++) {
                        int NewI = K;
                        int NewJ = J - K;

                        PointDef StaPoint = new PointDef() { X = LoopX - 1, Y = I };
                        PointDef EndPoint = new PointDef() { X = LoopX, Y = NewI };
                        PointDef CurrVector = SetVector(StaPoint, EndPoint);
                        double CurrCost = DeriveABS(CurrVector);
                        double NewValKouho = PrevDP[I, J].Value + CurrCost;
                        if (CurrDP[NewI, NewJ].HasValue) {
                            if (CurrDP[NewI, NewJ].Value <= NewValKouho) {
                                continue;
                            }
                        }
                        CurrDP[NewI, NewJ] = NewValKouho;
                    }
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[0, 0]);
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    static PointDef SetVector(PointDef pStaPoint, PointDef pEndPoint)
    {
        PointDef WillReturn;
        WillReturn.X = pEndPoint.X - pStaPoint.X;
        WillReturn.Y = pEndPoint.Y - pStaPoint.Y;
        return WillReturn;
    }

    // ベクトルの大きさを求める
    static double DeriveABS(PointDef pVector)
    {
        double wkNorm = DeriveNorm(pVector);
        double wkSqrt = Math.Sqrt(wkNorm);
        return wkSqrt;
    }

    // ベクトルのNormを求める
    static double DeriveNorm(PointDef pVector)
    {
        return pVector.X * pVector.X + pVector.Y * pVector.Y;
    }
}

解説

AArrの合計の割り振りの問題なので、

最小コスト[現在のY座標 , 残りのAVal]
を更新するDPで解いてます。