cafelier@SRM

AOJ1002: Extraordinary Grid I

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1002

import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.stdio;
import std.string;

void main()
{
   int t = readln().chomp().to!int();
   foreach(_; 0..t) {
      int N = readln().chomp().to!int();
      bool[] books = readln().chomp().map!"a=='Y'"().array();
      writeln(solve(N, books));
   }
}

int solve(int N, bool[] books)
{
   int[][] dp = new int[][](N+1, 3);
      // dp[x][y] = x列目の配達を終わらせてy行目で終わる最短距離

   foreach(y; 0 .. 3)
      dp[0][y] = 一列を最適に配る(0, y, books[0], books[2*N]);

   foreach(x; 1 .. N+1) {
      bool up = books[2*x-1];
      bool dn = books[2*x-1+2*N];
      if(2*x%(2*N) != 0) {
         up |= books[2*x];
         dn |= books[2*x+2*N];
      }
      foreach(y; 0 .. 3) {
         dp[x][y] = min(
            dp[x-1][0] + 1 + 一列を最適に配る(0, y, up, dn),
            dp[x-1][1] + 1 + 一列を最適に配る(1, y, up, dn),
            dp[x-1][2] + 1 + 一列を最適に配る(2, y, up, dn),
         );
      }
   }

   return dp[N][0];
}

int 一列を最適に配る(int スタート, int ゴール, bool 上の棚に本がある, bool 下の棚に本がある)
{
   int 歩行距離(int[] points)
   {
      int total = 0;
      foreach(i; 1..points.length)
         total += abs(points[i] - points[i-1]);
      return total;
   }

   if(上の棚に本がある && 下の棚に本がある)
      return min(歩行距離([スタート*2, 1, 3, ゴール*2]),
                 歩行距離([スタート*2, 3, 1, ゴール*2])) / 2;
   if(上の棚に本がある && !下の棚に本がある)
      return 歩行距離([スタート*2, 1, ゴール*2]) / 2;
   if(!上の棚に本がある && 下の棚に本がある)
      return 歩行距離([スタート*2, 3, ゴール*2]) / 2;
   return 歩行距離([スタート*2, ゴール*2]) / 2;
}

最後に、DPの書き方。書き方と言っても普通に配列を埋めるだけなのですが、多次元配列を new int[][](N+1, 3) のように一気に確保する書き方は便利です。というか、ないと大変です。変数名や関数名を一部日本語にしてみたのはギャグですので真似しないでください。いや、一人でコード読む分には割とたまに便利ですけど。