トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.258 回転寿司(2)
■■■問題■■■
あなたは、回転寿司にきている。
お寿司はN皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさがViで表される。
流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、
連続で皿を取ることが出来ない。
もちろん、自分の前を過ぎたお寿司も取ることが出来ない。
この時、あなたが得られる美味しさの最大の合計値と
取ったお皿の番号（1から始まる番号）を昇順に求めてください。
お寿司は一周回ってくることはないとする。
■■■入力■■■
N
V1 V2 V3 ・・・ VN
1行目に、お寿司の数N(1 <= N <= 1000)が与えられます。
2行目に、お寿司の美味しさ Vi(1 <= Vi <= 100,1 <= i <= N)が半角スペース区切りで与えれれます。
■■■出力■■■
1行目にあなたが得られる美味しさの最大の合計値と
2行目に取ったお皿の番号 (1-index) を空白区切りで出力してください。
答えが複数ある場合、どれか一つを出力してください。
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("1 2 3 4");
//6
//2 4
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("5 4 4 9");
//14
//1 4
}
else if (InputPattern == "Input3") {
WillReturn.Add("7");
WillReturn.Add("1 2 9 10 1 1 4");
//16
//2 4 7
}
else if (InputPattern == "Input4") {
WillReturn.Add("1");
WillReturn.Add("100");
//100
//1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] VArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
int UB = VArr.GetUpperBound(0);
//最大の美味しさ合計[添字]なDP表
var DPArr = new Nullable<int>[UB + 1];
//配るDPでの配布元の添字
int[] MotoIndArr = new int[UB + 1];
for (int I = 0; I <= UB; I++) MotoIndArr[I] = -1;
DPArr[0] = VArr[0];
if (UB > 0) DPArr[1] = VArr[1];
for (int I = 0; I <= UB; I++) {
Action<int> UpdateAct = (pNewInd) =>
{
if (pNewInd > UB) return;
int NewVal = DPArr[I].Value + VArr[pNewInd];
if (DPArr[pNewInd].HasValue == false
|| DPArr[pNewInd].Value < NewVal) {
DPArr[pNewInd] = NewVal;
MotoIndArr[pNewInd] = I;
}
};
UpdateAct(I + 2);
UpdateAct(I + 3);
//for (int J = 0; J <= UB; J++) {
// Console.WriteLine("DPArr[{0}]={1}", J, DPArr[J]);
//}
}
//UBかUB-1が最大値
int MaxSumVal = DPArr[UB].Value;
int CurrInd = UB;
if (UB > 0 && DPArr[UB - 1].Value > MaxSumVal) {
MaxSumVal = DPArr[UB - 1].Value;
CurrInd = UB - 1;
}
Console.WriteLine(MaxSumVal);
//DPの経路復元
var IndList = new List<int>();
while (CurrInd != -1) {
IndList.Add(CurrInd);
CurrInd = MotoIndArr[CurrInd];
}
var sb = new System.Text.StringBuilder();
for (int I = IndList.Count - 1; 0 <= I; I--) {
sb.Append(IndList[I] + 1);
if (I > 0) sb.Append(' ');
}
Console.WriteLine(sb.ToString());
}
}
解説