AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC404-E Bowls and Beans
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("1 1 2 1");
WillReturn.Add("1 0 0 1");
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("6");
WillReturn.Add("1 2 1 3 1");
WillReturn.Add("1 1 0 1 1");
//4
}
else if (InputPattern == "Input3") {
WillReturn.Add("16");
WillReturn.Add("1 1 1 2 5 1 1 3 4 1 4 3 1 1 2");
WillReturn.Add("1 0 0 0 1 0 0 1 1 0 0 0 0 0 1");
//7
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int[] mCArr;
static void Main()
{
List<string> InputList = GetInputList();
mCArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
int[] AArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
// 豆があるPosのList
var BeanPosList = new List<int>();
BeanPosList.Add(-1);
for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
if (AArr[I] > 0) {
BeanPosList.Add(I);
}
}
int Answer = 0;
int BeanPosList_UB = BeanPosList.Count - 1;
for (int I = 0; I <= BeanPosList_UB - 1; I++) {
int StaPos = BeanPosList[I + 1];
int EndPos = BeanPosList[I];
Answer += ExecDP(StaPos, EndPos);
}
Console.WriteLine(Answer);
}
// StaとEndを引数として、DPで移動コストを返す
static int ExecDP(int pStaPos, int pEndPos)
{
// 最小コスト[現在位置]なDP表
var PrevDP = new Dictionary<int, int>();
PrevDP[pStaPos] = 0;
int Answer = int.MaxValue;
while (PrevDP.Count > 0) {
var CurrDP = new Dictionary<int, int>();
foreach (var EachPair in PrevDP) {
int CurrPos = EachPair.Key;
int MoveCnt = mCArr[CurrPos];
for (int I = 1; I <= MoveCnt; I++) {
int ToPos = CurrPos - I;
if (ToPos < pEndPos) break;
int NewVal = EachPair.Value + 1;
if (NewVal >= Answer) {
continue;
}
// 枝切り
if (ToPos == pEndPos) {
Answer = Math.Min(Answer, NewVal);
continue;
}
if (CurrDP.ContainsKey(ToPos)) {
if (CurrDP[ToPos] <= NewVal) {
continue;
}
}
CurrDP[ToPos] = NewVal;
}
}
PrevDP = CurrDP;
}
return Answer;
}
}
解説
考察すると、
豆同士の間隔ごとに、DPで最小の移動コストを求めれば良いと分かります。