TCHS08 Online Round 3 Hard 練習

問題

正方形を無限にならべた横長の板があって、この上に高さが1で横の長さが決まっている長方形がいくつかある。この長方形を左右に動かして、ちょうど決められた範囲を覆うようにしたい。最低何回動かせばぴったり覆えるか求めなさい。

解

俺の嫁(動的計画法)の出番ですね。

i個の長方形を使って、aから n + width - 1 までを覆うようにしたときの最小移動回数を dp[i, n] とする。

最終的にbまで覆うとき、一番右の長方形の左端は b - width + 1 になるので、ここまで繰り返す。

それであとは隙間ができないようにいてれーしょん。

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

public class RectanglesArrangement {
    public int cover(int[] left, int width, int a, int b) {
        if (width > b - a + 1 || left.Length * width < b - a + 1)
            return -1;  // 不可能なので帰ってもらう

        int[,] dp = new int[51, 1001];

        for (int i = 0; i <= 50; i++)
            for (int j = 0; j <= 1000; j++)
                dp[i, j] = -1;

        Array.Sort(left);   // 長方形をソートしておく
        dp[1, a] = Math.Abs(left[0] - a);   // aに一番近い長方形をaにもっていく

        for (int i = 1; i < left.Length; ++i)
        {
            for (int j = a; j <= b - width + 1; ++j)    // 長方形を置ける範囲
            { 
                if(dp[i, j] != -1)
                {
                    for (int k = a; k <= b - width + 1; ++k)
                    {
                        if (k > j + width)
                            continue;  // 隙間を空けるなんて許さないんだからねっ
                        if(dp[i + 1, Math.Max(j, k)] == -1)
                            dp[i + 1, Math.Max(j, k)] = dp[i, j] + Math.Abs(left[i] - k);
                        else
                            dp[i + 1, Math.Max(j, k)] = Math.Min(dp[i + 1, Math.Max(j, k)], dp[i, j] + Math.Abs(left[i] - k));
                    }
                }
            }
        }
        return dp[left.Length, b - width + 1];
    }
}