AOJ 0530 Pyon-Pyon River Crossing

問題ページ
ぴょんぴょん川渡り | Aizu Online Judge

考えたこと

制約が色々小さくて最小コストを求めるので拡張dijkstraやDPを考える。 dp[i][j][k] = (i行目j列目まででk回一行飛ばしをしたときの最小滑りやすさ) としてDPを考えるとO(NMmax(k)^2)で計算量的には問題なさそう。岸から石に移るときの処理がうまくまとめられなかったので例外処理をする。こういうときはコメントを書くなり紙で整理してから実装しないとバグらせるので気をつけながらDPを書くと通った。
問題文が長くて実装面倒でICPCっぽさを感じた。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> stone[155];
int dp[155][15][100];
signed main(void)
{
  while(true) {
  int n, m;
  cin >> n >> m;
  if(!n) break;
  REP(i, n) {
    int k;
    cin >> k;
    stone[i].clear();
    REP(j, k) {
      int x, d;
      cin >> x >> d;
      stone[i].PB({x, d});
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  REP(i, stone[0].size()) dp[0][i][0] = 0;
  REP(i, stone[1].size()) dp[1][i][1] = 0;
  // i行目j列 一行飛ばしをk回やった
  REP(i, n-1) REP(j, stone[i].size()) REP(k, m+1) {
    if(dp[i][j][k] == 0x3f3f3f3f) continue;
    // (i, j)から一行飛ばししないとき
    // dp[i+1][l][k] を minで更新
    REP(l, stone[i+1].size()) {
      int dif = abs(stone[i][j].first - stone[i+1][l].first);
      int tmp = dif*(stone[i][j].second + stone[i+1][l].second);
      chmin(dp[i+1][l][k], dp[i][j][k] + tmp);
    }

    // (i, j)から一行飛ばしするとき
    // dp[i+2][l][k+1] を minで更新
    if(i == n-2 || k == m) continue;
    REP(l, stone[i+2].size()) {
      int dif = abs(stone[i][j].first - stone[i+2][l].first);
      int tmp = dif*(stone[i][j].second + stone[i+2][l].second);
      chmin(dp[i+2][l][k+1], dp[i][j][k] + tmp);
    }
  }

  // n-1行目のmin、n-2行目でm-1以下のmin
  int ret = INF;
  REP(i, stone[n-1].size()) REP(k, m+1) chmin(ret, dp[n-1][i][k]);
  REP(i, stone[n-2].size()) REP(k, m) chmin(ret, dp[n-2][i][k]);
  cout << ret << endl;
  }

  return 0;
}