帮忙解决一个DP问题

Question

我正在尝试解决 SPOJ 的问题（链接 ），可以这样简单地描述：给定 n 个间隔，每个间隔都有一个整数开始和结束，并给定最大时间的结束（我们称之为 max_end ），找出有多少种方法可以选择一组覆盖的间隔1...最大结束。间隔可能会重叠。我尝试过DP；首先按结束时间排序，然后 dp[ i ] 是一对，其中 dp[ i ].first 是覆盖 1...end[ i ] last 使用间隔 i 所需的最小间隔数dp[ i ].second 是执行此操作的方法数。这是我的主要 DP 循环：

for( int i = 1; i < n; i ++ ) {
    for( int j = 0; j < i; j ++ ) {
        if( ! ( x[ j ].end >= x[ i ].start - 1 ) )
            continue;
        if( dp[ j ].first + 1 < dp[ i ].first ) {
            dp[ i ].first = dp[ j ].first + 1;
            dp[ i ].second = dp[ j ].second;
        }
        else if( dp[ j ].first + 1 == dp[ i ].first ) {
            dp[ i ].second += dp[ j ].second;
        }
    }
}

不幸的是，它不起作用。有人可以告诉我哪里有错误吗？提前致谢！ :)

Answer 1

我不确定我是否理解您的解决方案想法，但我描述了我的 AC 解决方案：

我使用带有记忆功能的函数，但您可以使用非递归 DP 重写它。

假设我们的间隔位于数组对

a[100] 中；
在哪里
a[i].first 是间隔开始，a[i].second 是间隔结束。

首先按 begin 对该数组进行排序（具有默认对比较器的 stl 排序算法的默认行为）。

现在想象一下，我们从头到尾一个一个地“放置”间隔。

如果当前最后一个间隔是 x 并且前一个间隔是 'prev'，则让 f(int x, int prev) 返回完成填充的方式数。

我们将如下计算：

int f(int x, int prev) {
  // if already calculated dp[x][prev], return it. Otherwise, calculate it
  if (dp[x][prev] != -1) {
    return dp[x][prev];
  }
  if (a[x].second == m) {
    return dp[x][prev] = 1; // it means - X is last interval in day
  }
  else {
    dp[x][prev] = 0;
    for (int i = x + 1; i < n; ++i) { // try to select next interval
      if (a[i].first <= a[x].second && // there must be not empty space after x interval
          a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless
          a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless
          a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless.  
        dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000;
      }
    }
  }
  return dp[x][prev];
}

之后我们需要为每对间隔调用此函数，其中第一个从 0 开始，第二个与第一个连接：

for (int i = 0; i < n; ++i) {
  if (a[i].first == 0) {
     for (int j = i + 1; j < n; ++j) {
        if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless
            a[j].first <= a[i].second && // there must be no space after i interval
            a[j].second > a[i].second) { // in opposite case j will be useless
           res = (res + f(j, i)) % 100000000;
        }
     }
     // also we need to check the case when we use only one interval:
     if (a[i].second == m) {
        res = (res + 1) % 100000000;
     }
  }
}

之后我们只需要打印 res.