UVa12209

UVa12209
dp[配置済みの行数]

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int inf = 1 << 24;

const int N = 500 + 1;
int t[N];

set<int> word[N];

int rec(int curr, const int &fit, const int &line)
{
  if (line <= curr) return 0;
  if (t[curr] != inf) return t[curr];

  int mn = inf;
  set<int> ft;
  for (int i = curr; i < line; ++i) {
    ft.insert(word[i].begin(), word[i].end());
    if (fit < ft.size() + (i - curr + 1)) break;
    mn = min(mn, rec(i + 1, fit, line) + (int)ft.size());
  }

  return t[curr] = mn;
}

int main(void)
{
  int tc;
  cin >> tc;
  while (tc--) {
    fill(word, word + N, set<int>());
    fill(t, t + N, inf);

    int n, s, w;
    cin >> n >> s >> w;
    
    for (int i = 0; i < w; ++i) {
      int m;
      cin >> m;
      while (m--) {
        int no;
        cin >> no;
        word[no - 1].insert(i);
      }
    }

    static int cnt = 0;
    int result = rec(0, s, n);
    cout << "Case " << ++cnt << ": " << (result == inf ? -1 : result) << endl;
  }
  return 0;
}