帮助解决DP问题

Question

我正在尝试解决SPOJ(链接)中的一个问题,可以简单地描述如下:给定n个区间,每个区间都有一个整数开头和结尾,并给定最终时间结束(让我们称之为max_end),找到有多少种方法可以选择一组覆盖1 ... max_end的区间.间隔可能重叠.我试过DP; 首先按结束时间排序,然后dp [i]是一对,其中dp [i] .first是覆盖1 ... end [i] 最后使用间隔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 是间隔结束。

首先开始排序此数组（具有默认对比较器的 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.