DPコンテスト
次のDPコンテストの問題へ
前のDPコンテストの問題へ
Educational DP Contest B Frog2
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 3");
WillReturn.Add("10 30 40 50 20");
//30
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 1");
WillReturn.Add("10 20 10");
//20
}
else if (InputPattern == "Input3") {
WillReturn.Add("2 100");
WillReturn.Add("10 10");
//0
}
else if (InputPattern == "Input4") {
WillReturn.Add("10 4");
WillReturn.Add("40 10 20 70 80 10 20 70 80 60");
//40
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
int K = wkArr[1];
int[] HArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
int UB = HArr.GetUpperBound(0);
// 最小コスト[現在位置] なDP表
var DPDict = new Dictionary<int, int>();
DPDict[0] = 0;
for (int I = 0; I <= UB; I++) {
if (DPDict.ContainsKey(I) == false) continue;
Action<int> wkAct = (pNewInd) =>
{
if (pNewInd > UB) return;
int NewVal = DPDict[I] + Math.Abs(HArr[I] - HArr[pNewInd]);
if (DPDict.ContainsKey(pNewInd)) {
if (DPDict[pNewInd] <= NewVal) {
return;
}
}
DPDict[pNewInd] = NewVal;
};
for (int J = 1; J <= K; J++) {
wkAct(I + J);
}
}
Console.WriteLine(DPDict[UB]);
}
}
解説
DPで解いてます。