第2回 CodeIQプロコン 4問目 ハリセンボンアタック

■■■問題■■■

カメと協力して怪物と戦います。

攻撃手段は、ハリセンボンを捕まえて怪物に投げつけるという方法です。
ただし、ハリセンボンを捕まえるときにあなた・カメ共にいくらかのダメージを受けます。
自分たちが生き残る最低限の体力は残しつつ、怪物にできるだけ大きなダメージを与えてください。

あなた・カメの体力をそれぞれ100と数値化します。
ハリセンボンは何匹かいますが、
怪物に与えるダメージ・あなたが受けるダメージ・カメが受けるダメージは異なっており、
それらはハリセンボン1匹ごとに数値化されたデータセットとして与えられます。

■■■入力■■■

標準入力の1行目に、ハリセンボンの数を表す整数値N（10 <= N <= 50）が与えられます。

2行目以降のN行に、
怪物に与えるダメージ・あなたが受けるダメージ・カメが受けるダメージを表す3つの整数値が
半角スペース区切りで与えられます。

■■■出力■■■

あなた・カメが共に生き残っている(それぞれ体力値が1以上残っている)状態で、
怪物に与えうる最大ダメージを出力してください。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("10");
            WillReturn.Add("100 10 10");
            WillReturn.Add("120 12 9");
            WillReturn.Add("90 8 9");
            WillReturn.Add("150 16 17");
            WillReturn.Add("145 10 19");
            WillReturn.Add("300 32 27");
            WillReturn.Add("190 15 20");
            WillReturn.Add("170 16 18");
            WillReturn.Add("220 28 15");
            WillReturn.Add("280 31 32");
            //1015
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct DamageInfoDef
    {
        internal int Kaibutu;
        internal int Urashima;
        internal int Kame;
    }

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

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

        var DamageInfoList = new List<DamageInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            DamageInfoDef WillAdd;
            WillAdd.Kaibutu = wkArr[0];
            WillAdd.Urashima = wkArr[1];
            WillAdd.Kame = wkArr[2];
            DamageInfoList.Add(WillAdd);
        }

        //怪物のダメージ[浦島のダメージ,亀のダメージ]なDP表
        int UB = 100 - 1;
        var DP = new Nullable<int>[UB + 1, UB + 1];
        DP[0, 0] = 0;

        int MaxVal = 0;
        foreach (DamageInfoDef EachDamageInfo in DamageInfoList) {
            for (int X = UB; 0 <= X; X--) {
                for (int Y = UB; 0 <= Y; Y--) {
                    if (DP[X, Y] == null) continue;

                    int NewX = X + EachDamageInfo.Urashima;
                    int NewY = Y + EachDamageInfo.Kame;

                    if (UB < NewX || UB < NewY) continue;

                    int NewVal = DP[X, Y].Value + EachDamageInfo.Kaibutu;

                    if (DP[NewX, NewY] == null || DP[NewX, NewY] < NewVal) {
                        DP[NewX, NewY] = NewVal;
                        if (MaxVal < NewVal)
                            MaxVal = NewVal;
                    }
                }
            }
        }
        Console.WriteLine(MaxVal);
    }
}

解説

動的計画法で怪物のダメージ[浦島のダメージ,亀のダメージ]を
順次更新してます。