leetcode-go/poj/1463.strategic-game/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1500;
const int INF = 0x3F3F3F3F;

struct Node {
  short par;
  short cnt;
  short nxt[10];
} tree[N];

int dp[N][2];

void tree_dp(int id) {
  if (tree[id].cnt == 0) {
    dp[id][true] = 1;
    dp[id][false] = 0;
    return;
  }
  for (int i = 0, c = tree[id].cnt; i < c; i++) {
    int nxt = tree[id].nxt[i];
    tree_dp(nxt);
    if (i == 0) {
      dp[id][false] = dp[nxt][true];
      dp[id][true] = min(dp[nxt][true], dp[nxt][false]) + 1;
    } else {
      dp[id][false] += dp[nxt][true];
      dp[id][true] += min(dp[nxt][true], dp[nxt][false]);
    }
  }
  return;
}

int main() {
  int n, a, b, c;
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; i++) tree[i].par = -1;
    for (int i = 0; i < n; i++) {
      scanf("%d:(%d)", &a, &b);
      tree[a].cnt = b;
      for (int j = 0; j < b; j++) {
        scanf("%d", &c);
        tree[a].nxt[j] = c;
        tree[c].par = a;
      }
    }
    memset(dp, 0x3F, sizeof(dp));
    int root = 0;
    while (tree[root].par != -1) root = tree[root].par;
    tree_dp(root);
    printf("%d\n", min(dp[root][true], dp[root][false]));
  }
  return 0;
}