AOJ 0673 いちご

問題へのリンク

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("10");
            WillReturn.Add("1 3");
            WillReturn.Add("2 1");
            WillReturn.Add("3 4");
            WillReturn.Add("4 1");
            WillReturn.Add("5 5");
            WillReturn.Add("6 9");
            WillReturn.Add("7 2");
            WillReturn.Add("8 6");
            WillReturn.Add("9 5");
            WillReturn.Add("10 3 ");
            //20
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("0 450");
            WillReturn.Add("5 445");
            WillReturn.Add("10 430");
            WillReturn.Add("15 405");
            WillReturn.Add("20 370");
            WillReturn.Add("25 325");
            WillReturn.Add("30 270");
            WillReturn.Add("35 205");
            WillReturn.Add("40 130");
            WillReturn.Add("45 45 ");
            //450
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15");
            WillReturn.Add("11 23");
            WillReturn.Add("3 94");
            WillReturn.Add("89 3");
            WillReturn.Add("38 58");
            WillReturn.Add("65 29");
            WillReturn.Add("41 3");
            WillReturn.Add("80 42");
            WillReturn.Add("22 76");
            WillReturn.Add("48 85");
            WillReturn.Add("83 98");
            WillReturn.Add("87 29");
            WillReturn.Add("97 96");
            WillReturn.Add("22 75");
            WillReturn.Add("57 25");
            WillReturn.Add("99 33 ");
            //198
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct IchogoInfoDef
    {
        internal long Pos;
        internal long Time;
    }
    static List<IchogoInfoDef> mIchogoInfoList = new List<IchogoInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr.Trim());
            IchogoInfoDef WillAdd;
            WillAdd.Pos = wkArr[0];
            WillAdd.Time = wkArr[1];
            mIchogoInfoList.Add(WillAdd);
        }

        mIchogoInfoList = mIchogoInfoList.OrderBy(pX => pX.Pos).ToList();
        int UB = mIchogoInfoList.Count - 1;
        long CurrTime = mIchogoInfoList[UB].Pos;

        for (int I = UB; 0 <= I; I--) {
            // 待機が必要なら待機
            if (CurrTime < mIchogoInfoList[I].Time) {
                CurrTime = mIchogoInfoList[I].Time;
            }

            // 移動コスト
            if (I > 0) {
                CurrTime += mIchogoInfoList[I].Pos - mIchogoInfoList[I - 1].Pos;
            }
            else {
                CurrTime += mIchogoInfoList[I].Pos;
            }
        }
        Console.WriteLine(CurrTime);
    }
}

解説

いちごの収穫にかかる時間は0なので、
考察すると、下記の貪欲法が最適だと分かります。

右端のいちごまで移動した後、
必要に応じて待機しながら、左に移動し、
いちごを収穫する。