TopCoder SRM 145 DIV 1 Hard 練習

問題

与えられた長さの間で、一番高い部分が決められた高さで、かつ高さの決まってる標識が全て現れるような丘は何通りあるか。

解

俺の嫁でおなじみの動的計画法のご登場です。

残りの長さがlで、現在の高さがhで、今までに現れた標識の数がnで、一番高い部分をまだ通過していない状態における組合せを dp[l][h][n][0] 、一番高い部分を通過したあとの状態を dp[l][h][n][1] とする。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class HillHike {
    long[, , ,] dp;
    bool[, , ,] got;
    int[] lms;
    int maxh;
    int dist;

    public long numPaths(int distance, int maxHeight, int[] landmarks) {
        dp = new long[101, 51, 51, 2];
        got = new bool[101, 51, 51, 2];
        dist = distance;
        lms = landmarks;
        maxh = maxHeight;
        return rec(distance, 0, 0, 0);
    }

    private long rec(int left, int height, int landm, int reached)
    {
        if (left == 0)  // おわり
        {
            if (height > 0 || landm < lms.Length || reached == 0)
                return 0;
            return 1;
        }

        if (height == 0 && left < dist)
            return 0;

        if (got[left, height, landm, reached])
            return dp[left, height, landm, reached];
        got[left, height, landm, reached] = true;
        dp[left, height, landm, reached] = 0;

        int next = landm;
        if (landm < lms.Length && height == lms[landm]) // landmark発見
            next++;

        int isreached = reached;
        if(height == maxh)  // てっぺん到達
            isreached = 1;

        if (height > 0)  // type 3
            dp[left, height, landm, reached] += rec(left - 1, height - 1, next, isreached);
        dp[left, height, landm, reached] += rec(left - 1, height, next, isreached); // type 2
        if (height < maxh)   // type 1
            dp[left, height, landm, reached] += rec(left - 1, height + 1, next, isreached);
        return dp[left, height, landm, reached];
    }
}