题解：P14259 兄妹（siblings）

· · 题解

这篇题解是对第二篇题解的补充说明。这里推一下我的博客。

分析

这里有一个贪心策略：如果有一个人要进入某一行，他就必须把这一行的所有书本全部放进去。证明：这里考虑反证法。如果肯定有一个人需要到达最远的地方放书，那么他一定路过其他的书，也就可以帮另一个人放了，所以如果这个人进去了，另一个人就一定不需要进入这一行。所以我们就可以发现只需要记录每一行最远的书在哪里就可以了，因为 r_i \leq 500，肯定是没有问题的。所以这时候对于每一个人，他在某个书架只有进去和不进去两种情况（不进去的全部让另一个人进去），这里很明显就是一个01背包的存在性问题。

01背包

会01背包的童鞋们可以跳过这一段。

01背包解决的问题就是：给你 n 个物品，每个物品有一个价值 v_i 和一个重量 w_i，每个物品都有选和不选两种情况，求在一个背包可以承受的重量 W 内可以获得的最大价值。

暴力是很简单的，可以直接用01DFS选择，这时候我们发现，当 i<j 时，按顺序遍历到的 j 的选择（选还是不选）是不会影响到 i 的选择的，所以如果我们开一个数组，记录它选前 j 个的最大价值也肯定是不会影响选前 i 个的最大价值的，这也就是动态规划的无后效性。

我们又发现，如果我们把选 N 个物品变成选 1 个物品，然后 2 个，再 3 个，最后 N 个，我们是可以通过前面的得到的答案来得到最终整个问题的答案的，这也就是动态规划的最优子结构。

我们还知道，在暴力中有一种东西叫做记忆化搜索，就是把之前的答案存起来可以让他不用重复计算，我们开数组就可以把之前的存起来，然后方便后面使用，这就是动态规划的子问题重叠性。

我们发现01背包刚好满足这三个性质，所以我们可以使用动态规划。因为影响背包价值的只有抉择了哪些物品和这些物品的重量，所以我们定义 dp[i][j] 为抉择前 i 个物品总共凑出 j 的重量的最大价值。转移就是 dp[i][j]=max({dp[i][j],dp[i-1][j],dp[i-1][j-w[i]]+v[i]})，dp[i-1][j] 就是不选，最后一个就是选。于是我们有了这份代码：

void DP() {
  for (int i=1;i<=n;i++) {
    for (int j=W;j>=w[i];j--) {
      dp[i][j]=max({dp[i][j],dp[i-1][j],dp[i-1][j-w[i]]+v[i]});
    }
  }
}

又因为 dp[i] 的所有结果只会被 dp[i-1] 的结果所影响，所以可以使用滚动数组。

void DP() {
  for (int i=1;i<=n;i++) {
    for (int j=W;j>=w[i];j--) {
      dp[i%2][j]=max({dp[i%2][j],dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]]+v[i]});
    }
  }
}

回到这道题，我们可以把问题从最大的价值转换成可以拼成什么价值，类似求给出 n 个物品的重量，现在有一个容量（其中一个人走的）为 W 的背包最少空出的格子的问题，相当于用背包标记某种状态是否可行而不是最大价值。

void DP() {
  for (int i=1;i<=n;i++) {
    for (int j=W;j>=w[i];j--) {
      dp[i%2][j]=dp[(i-1)%2][j];
      dp[i%2][j]|=dp[(i-1)%2][j-w[i]]+v[i]});
    }
  }
}

只不过这里因为是求两者的最大值最小，就是看每种情况是否可行，如果可行，当前的重量和剩余的重量取最大值就是当前的答案，每次都取最小值就可以了。

思路总结

首先我们可以先求出每一行的最大的 c_i，然后使用01背包检查前 i 个第一个人放一些书走 j 的路程（只包括进入书架后的）是否可行，如果可行，那么算出两者的路程，第一个人就是进入书架的路程再加上里面的路程 i+j，第二个人一定是会走到底的，下面的路程是 n（n 就是最大的 r_i），上面的路程是 sumc-j，这里 sumc 是前 i 行的进入书架的路程的和，我们可以边做背包边验证（记录答案），我们可以只记录单程，然后乘 2 就可以了。

Q：为什么要乘 2 呢？

A：看下面这个例子：

  |         |
  | |   |   |
-------------
0 1 2 3 4 5 6

假设一个人从第 0 行走到了第 i 行，前面走进去放书的路程是 j，那么我们可以记录他的时间是 i+j，然后 *2 即可。

核心代码如下：

for (int i=1;i<=n;i++) {
    if (!h[i]) continue;
    for (int j=sum;j>=0;j--) {
        dp[i%2][j]|=dp[(i-1)%2][j];
        dp[i%2][j+h[i]]|=dp[i%2][j];
    }
    sum+=h[i];
    for (int j=0;j<=sum;j++) {
        if (dp[i%2][j]) {
            ans=min(ans,max(i+j,n+sumc-j));
        }
    }
}

代码

int dp[2][maxv*maxv]; 
void solve() {
    memset(dp,0,sizeof(dp)); // 记得初始化
    int t; cin >> t;
    vector<int> h;
    for (int i=1;i<=t;i++) {
        int r,c; cin >> r >> c;
        if (h.size()<r+1) h.resize(r+1);
        h[r]=max(h[r],c);
    }    
    int n=h.size()-1;
    int sum=0;
    int sumc=0; 
    int ans=1e9;
    dp[0][0]=1;
    for (int i=1;i<=n;i++) sumc+=h[i];
    for (int i=1;i<=n;i++) {
        if (!h[i]) continue;
        for (int j=sum;j>=0;j--) {
            dp[i%2][j]|=dp[(i-1)%2][j];
            dp[i%2][j+h[i]]|=dp[i%2][j];
        }
        sum+=h[i];
        for (int j=0;j<=sum;j++) {
            if (dp[i%2][j]) { 
                ans=min(ans,max(i+j,n+sumc-j));
            }
        }
    }
    cout << 2*ans << endl; 
}