第6回PAST K 共通クーポン

問題へのリンク

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("3");
            WillReturn.Add("50 40");
            WillReturn.Add("30 29");
            WillReturn.Add("60 55");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("652 175");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("859 346");
            WillReturn.Add("669 705");
            WillReturn.Add("344 425");
            WillReturn.Add("693 747");
            WillReturn.Add("24 808");
            WillReturn.Add("462 344");
            WillReturn.Add("930 67");
            WillReturn.Add("878 35");
            WillReturn.Add("906 253");
            WillReturn.Add("531 832");
            //1696
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PUInfoDef
    {
        internal int Diff;
        internal int P;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        var PUInfoList = new List<PUInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PUInfoDef WillAdd;
            WillAdd.P = wkArr[0];
            WillAdd.Diff = wkArr[1] - wkArr[0];
            PUInfoList.Add(WillAdd);
        }

        // 最大スコア[P合計]なDP表
        var PrevDP = new Dictionary<int, int>();
        PrevDP[0] = 0;

        foreach (PUInfoDef EachPUInfo in PUInfoList) {
            var CurrDP = new Dictionary<int, int>(PrevDP);
            foreach (var EachPair in PrevDP) {
                int NewKey = EachPair.Key + EachPUInfo.P;
                int NewVal = EachPair.Value + EachPUInfo.Diff;

                if (NewKey >= 100) {
                    NewVal += NewKey / 100 * 20;
                    NewKey %= 100;
                }
                if (CurrDP.ContainsKey(NewKey)) {
                    if (CurrDP[NewKey] >= NewVal) {
                        continue;
                    }
                }
                CurrDP[NewKey] = NewVal;
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Values.Max());
    }
}

解説

最大スコア[P合計]を更新するDPで解いてます。
状態数の削減で、P合計はmod100で持ってます。