AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC369-D Bonus EXP
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 5 3 2 7");
//28
}
else if (InputPattern == "Input2") {
WillReturn.Add("2");
WillReturn.Add("1000000000 1000000000");
//3000000000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
// スコア[次に倒すモンスター]なDP表
var PrevDP = new Dictionary<long, long>();
PrevDP[1] = 0;
foreach (long EachA in AArr) {
var CurrDP = new Dictionary<long, long>(PrevDP);
foreach (var EachPair in PrevDP) {
long NewVal = EachPair.Value + EachA;
if (EachPair.Key == 2) {
NewVal += EachA;
}
long NewKey = EachPair.Key + 1;
if (NewKey == 3) NewKey = 1;
if (CurrDP.ContainsKey(NewKey)) {
if (CurrDP[NewKey] >= NewVal) {
continue;
}
}
CurrDP[NewKey] = NewVal;
}
PrevDP = CurrDP;
}
Console.WriteLine(PrevDP.Values.Max());
}
}
解説
スコア[次に倒すモンスター]でDPしてます。