每周解题报告 (4th, 8/20~9/10)

2017-09-10 oi algorithm Comments Word Count: 4142words Read Count: 9minutes

经过了一周阶段考的折磨过后，这一周终于有时间更新解题报告了。上一周因为时间太少，加上填 MUSE 的坑，只做了一题，索性都屯到这一周来发了，但虽然这样这周的题量还是没有多到哪里去……

有些比较简单的题目我就两句话带过就好了。特地在 GitHub 上开了个仓库，这一篇包括之前那些解题报告中题目的所有完整代码（以及部分题的数据）以及接下来做的 HDU 的题都会汇总在这个地方。

¹³⁄₂₀₀, HDU1069, Monkey and Banana

Solution

经典 DP，最开始的思路是……设一个四维的状态…反正数据范围这么小是吧 (x) 后来写了好久写不下去了。查了一发题解，随便点开一个，看到第一句话：先把 x 排序，然后把 y 排序……会了……

那么，首先输入一组 xyz，然后排序一下，选择其中两个当做 width 和 length，然后最后一个数当 height；把 x, y 分别按照从大到小的顺序排序一遍，然后对 z 求满足第 i 层的 x, y 小于第 i-1 层的 x, y 时的最大 z 之和就好了。

转移方程：dp[i] = dp[j] + block[i].height, 其中 j = 0...i-1

*// PS. 嘛，顺序枚举 j 似乎会 WA，所以 j 要从 i-1 倒回去。 *

Code

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 35 * 6 + 10;
struct Block {
  int x, y, z;
};
Block b[MAXN];
int T, kases = 0;
int size = 0, ans = 0;
int dp[MAXN];

bool cmp(const Block a, const Block b)
{
  if (a.x > b.x)
    return true;
  if (a.x == b.x && a.y > b.y)
    return true;
  return false;
}

int main()
{
  while (scanf("%d", &T) != EOF && T != 0)
  {    
    size = 0, ans = 0;
    memset(b, 0, sizeof(b));
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i < T; i++)
    {
      int tx, ty, tz;
      scanf("%d%d%d", &tx, &ty, &tz);
      int arr[3] = {tx, ty, tz};
      
      sort(arr, arr + 3);
      
      // permutation
      b[size].x = arr[0], b[size].y = arr[1], b[size++].z = arr[2];
      b[size].x = arr[0], b[size].y = arr[2], b[size++].z = arr[1];
      b[size].x = arr[1], b[size].y = arr[2], b[size++].z = arr[0];
      
      sort(b, b+size, cmp);
    }
    
    for (int i = 0; i < size; i++)
    {
      dp[i] = b[i].z;
      for (int j = i - 1; j >= 0; j--)
      {
        if (b[i].x < b[j].x && b[i].y < b[j].y) {
          dp[i] = max(dp[j] + b[i].z, dp[i]);
        }
      }
      ans = max(ans, dp[i]);
    }
    printf("Case %d: maximum height = %d\n", ++kases, ans);
  }
  return 0;
}

¹⁴⁄₂₀₀, HDU1176, 免费馅饼

Solution

这题有两种做法。

第一种是直接 DP，注意的是可以不要想太多去检查状态是否合法，状态表示和转移方程：dp[i][j] 表示第 i 秒的时候站在第 j 个位置能接到的最大馅饼数，则：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + items[i][j] (如果 j-1 和 j+1 存在)
数塔做法：联想一下数字三角形，从下往上递推回去就行了。dp[i][j] 还是表示第 i 秒在第 j 个位置能取到的最大值，不同的是要逆推，并且可以直接覆盖掉之前的值（因为计算完就没有用了），则：
```
## Code
```
cpp

// Solution 1 #include using namespace std;

const int MAXT = 1e5 + 10; const int MAXP = 11;

int n, mt, ans = 0; int items[MAXT][MAXP]; int dp[MAXT][MAXP];

int cmp(int a, int b, int c) { return max(a, max(b, c)); }

int main() { while (scanf(“%d”, &n) != EOF && n != 0) { memset(items, 0, sizeof(items)); memset(dp, 0, sizeof(dp)); mt = 0, ans = 0; for (int i = 0; i < n; i++) { int x, t; scanf(“%d%d”, &x, &t); items[t][x]++; mt = max(t, mt); }

dp[1][4] = items[1][4];
dp[1][5] = items[1][5];
dp[1][6] = items[1][6];

for (int i = 2; i <= mt; i++)
{
  for (int j = 0; j < MAXP; j++)
  {
    dp[i][j] = dp[i-1][j];
    if (j == 0) {
      dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]) + items[i][j];
    } else if (j == MAXP - 1) {
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + items[i][j];
    } else {
      dp[i][j] = cmp(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + items[i][j];
    }
    ans = max(ans, dp[i][j]);
  }
}

printf("%d\n", ans);

} return 0; }

cpp // Solution 2 #include using namespace std; const int MAXT = 1e5 + 10; const int MAXP = 11;

int n, mt, ans = 0; int pies[MAXT][MAXP];

int main() { while (scanf(“%d”, &n) != EOF && n) { memset(pies, 0, sizeof(pies)); ans = 0; for (int i = 0; i < n; i++) { int x, t; scanf(“%d%d”, &x, &t); pies[t][x]++; mt = max(mt, t); }

for (int i = mt - 1; i >= 0; i--)
{
  for (int j = 0; j < MAXP; j++)
  {
    int tmp = pies[i][j];       // current
    pies[i][j] = pies[i+1][j];

    if (j > 0) {
      pies[i][j] = max(pies[i+1][j-1], pies[i][j]);
    }

    if (j < MAXP - 1) {
      pies[i][j] = max(pies[i+1][j+1], pies[i][j]);
    }

    pies[i][j] += tmp;
  }
}

printf("%d\n", pies[0][5]);

} return 0; }

# 15/200, Codeforces 846A, Curriculum Vitae

## Solution
题意就是一个人要找工作，要在简历上介绍他所完成过的游戏，游戏有成功的和失败的，这个人不想让任何失败的游戏出现在成功的游戏之后，然后求他最多可以在他的简历上放上多少个这样的符合要求的游戏。

↑ 说成人话就是：求一个由 0 和 1 组成的序列的子序列，这个子序列满足没有一个 0 在 1 的右边，且长度尽可能大。例如 0 1 0 0 1 0 的符合要求的子序列为 0 0 0 1 或 0 0 0 0.

翻译完之后我们可以发现，只要找到一个最长的数列的，使得它的左边都是 0，右边都是 1 就可以了。然后我们可以发现这个子序列满足**最长不下降（注意不是最长上升）**的性质。鉴于数据范围 <= 100，所以我们可以用 O(n^2) 的最长不下降子序列算法直接过。

第二天想了一下，突然觉得这题似乎还有线性的做法：考虑第 i 件作品是否入选，和它的上一件符合性质要求的作品有关。假如第 i 件作品是失败的，那么第 i 件写入简历时，最大值为 **上一件失败作品的最大值 + 1**；如果第 i 件作品是成功的，那么第 i 件写入简历时最大值为 **上一件失败作品的最大值 和 上一件成功作品的最大值 两者的最大值 + 1**。这样，我们可以用一个 ```last0``` 表示上一件失败作品的位置，用 ```last1``` 表示上一件成功作品的位置。具体的转移方程可以看代码：

## Code

cpp // Solution 1: O(n^2) #include using namespace std; const int MAXN = 105; const int INF = 1e9 + 7; int n, ans = 0; int arr[MAXN]; int dp[MAXN]; int main() { memset(arr, 0, sizeof(arr)); memset(dp, 0, sizeof(dp));

scanf(“%d”, &n); for (int i = 0; i < n; i++) { scanf(“%d”, &arr[i]); }

for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (arr[j] <= arr[i] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } ans = max(dp[i], ans); }

printf(“%d”, ans);

return 0; }

cpp // Solution 2: O(n) #include using namespace std; const int MAXN = 105; int n; int dp[MAXN]; int last0 = -1, last1 = -1; int main() { memset(dp, 0, sizeof(dp)); scanf(“%d”, &n); for (int i = 0; i < n; i++) { int tmp; scanf(“%d”, &tmp); if (tmp == 0) { dp[i] = (last0 == -1 ? 1 : dp[last0] + 1); last0 = i; } else { if (i == 0) { dp[i] = 1; } else { dp[i] = 1; if (last0 != -1) { dp[i] = max(dp[last0] + 1, dp[i]); } if (last1 != -1) { dp[i] = max(dp[last1] + 1, dp[i]); } } last1 = i; } } int ans = 0; for (int i = 0; i < n; i++) { ans = max(ans, dp[i]); } printf(“%d”, ans); return 0; }


# 16/200, Codeforces 854A, Fraction

嗯……太水了，不想写了，就是单纯的计算。

cpp #include const int INF = 1e9 + 7; int gcd(int a, int b) { return (a == 0) ? b : gcd(b % a, a); } int main() { int ori, curi = 1, curj = INF;

scanf(“%d”, &ori); for (int i = 1; i < ori; i++) { for (int j = i + 1; j < ori; j++) { int gcder = gcd(j, i); double a = (double) i, b = (double) j;

  if (
    (i + j) == ori &&
    gcder == 1 &&
    (double)(a / b) > (double)((double)curi / (double)curj)
  ) {
    curi = i, curj = j;
  }
}

}

printf(“%d %d”, curi, curj); return 0; }


# 17/200, HDU4568, Hunter

这题前前后后花了我两星期的时间……这星期又花了三天的时间看它，终于理解并且 A 掉了这题……果然状态压缩还是一个大坑 Orz……

## Solution
题目大意是给定一个 n*m 的地图，其中有一些点当中有宝藏，经过地图中的每个点都需要花费相应的代价。一个人要从边界进入这个地图，经过所有的宝藏点，然后从边界走出，问这样做的最小代价是多少。n, m <= 200, 宝藏数目 1 <= k <= 13.

首先题目的模型说成人话就是从边界的任何一点进入，取走所有宝藏，然后从边界的任意一点走出，所以我们可以知道最小代价应该是：从边界到第一个点的代价+第一个点到第二个点的代价+……+从终点走出边界的代价，这样这道题就被我们分解成了一个个的子问题了，我们只需要分别计算这些子问题就可以了。现在：

1. 从边界到第一个点的最小代价和从终点走出的边界如何知道？从第 i 个点到第 j 个点的最小代价又如何知道？SPFA 对每一个宝藏点跑一遍就行了，这样我们总共需要进行 k 次 SPFA。

2. 如何决策？每次拓展都选择当前一步代价最小的方案走显然有可能不是最优解，所以我们还是用动态规划来解全局最优的最小代价。

3. 用 DP 如何表示状态？这道题的要求是走完所有的宝藏点，那么我们首先考虑如何表示经过的和未经过的宝藏点。因为 k <= 13，我们的第一反应应该是状态压缩。用二进制表示状态点的经过情况，二进制第 i 位为 0 表示未经过第 i 个宝藏点，为 1 则表示已经经过，然后把二进制状态转换成十进制的整数即可。还有一个问题，假如只设置这样的一个状态，那么只能表示经过的点情况，不能表示终点在哪一个点，而我们到达终点的时候还需要从边界走出去，这样就还差一步，所以我们再设计一维状态，那么：

> 设 ```dp[i][j]``` 为当前经过的点状态为 i 且最后所在的终点位置为 j 时，所花费的最小代价。这样我们还能顺便得到转移方程：```dp[s | (1 << next)][next] = min(dp[s | (1 << next)][next], dp[s][cur] + toEach[cur][next])```, 其中 s 是当前状态，cur 是当前状态的终点，next 是下一步的点。

（为什么这里不需要表示起点？因为我们用 ```dp[1 << i][i] = toEdge[i]``` 可以很容易地表示以第 i 个点为起点时的代价，又我们的状态从 0 开始，所以起点在哪可以直接决策；但是终点我们很难通过 DP 方程直接决策，所以我们多一维状态。）

首先我们用 SPFA 先求出每两个宝藏点之间的距离和每个宝藏点到边界的距离（注意节点的拓展方向），然后就可以状态压缩了。DP 完之后，别忘了要回到边界，所以最终 ```ans = min(dp[(1 << k) - 1][i] + toEdge[i], ans), 其中 i = 0...k```.

这样我们就完美地解决了这个问题。

## Code

cpp #include using namespace std; const int INF = 1e9 + 7; const int MAXN = 205; const int MAXT = 14;

struct Point { int x, y; }; Point target[MAXT]; // 宝藏坐标

int k, cases, row, col;

// dp[i][j] 表示当前已经过的宝藏点状态为 i, 并且终点为 j 时所花费的最小代价 // 那么有 DP 方程：dp[s|(1<<next)][next] = min(dp[s|(1<<next)][s], dp[s][cur] + toEach[cur][next]); // 其中 next 是下一个目标状态点，cur 是当前状态的终点 int dp[1 << MAXT][MAXT];

// 用于 SPFA 计算每个宝藏点之间的距离 int dist[MAXN][MAXN];

// toEdge[i] 表示第 i 个宝藏点到边界的最小代价（不包括本身） // toEach[i][j] 表示第 i 个宝藏点到第 j 个宝藏点的最小代价 int toEdge[MAXT], toEach[MAXT][MAXT];

// SPFA 拓展节点的方向 int dir[2][4] = { { 0, 0, 1, -1 }, { 1, -1, 0, 0 } };

// SPFA 记录点访问情况的数组 bool vis[MAXN][MAXN];

// 用不定长数组存储地图 vector G[MAXN];

void SPFA(int s) { // 初始化 SPFA memset(vis, 0, sizeof(vis)); for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) dist[i][j] = INF;

queue Q;

Point start; start.x = target[s].x, start.y = target[s].y; vis[start.x][start.y] = 1; // 标记起点为已访问 dist[start.x][start.y] = 0; // 起点到自身的最短路为 0 Q.push(start);

while (!Q.empty()) { Point cur = Q.front(); Q.pop(); vis[cur.x][cur.y] = 0; // 当前节点出队，标记为未访问

// 到达边界，更新该点到边界的距离
if (cur.x == 0 || cur.y == 0 || cur.x == row - 1 || cur.y == col - 1) {
  toEdge[s] = min(toEdge[s], dist[cur.x][cur.y]);
}

// 拓展节点
for (int i = 0; i < 4; i++)
{
  Point next;
  next.x = cur.x + dir[0][i], next.y = cur.y + dir[1][i];
  // 检验节点合法性以及是否可到达
  if (next.x >= 0 && next.y >= 0 && next.x < row && next.y < col && G[next.x][next.y] != -1) {
    // 松弛操作
    if (dist[next.x][next.y] > dist[cur.x][cur.y] + G[next.x][next.y]) {
      dist[next.x][next.y] = dist[cur.x][cur.y] + G[next.x][next.y];
      if (!vis[next.x][next.y]) {
        Q.push(next);
        vis[next.x][next.y] = 1;
      }
    }
  }
} // end for i

} // end while }

void init() { for (int i = 0; i < MAXN; i++) G[i].clear();

for (int i = 0; i < (1 << MAXT); i++) for (int j = 0; j < MAXT; j++) dp[i][j] = INF;

fill(toEdge, toEdge + MAXT, INF);

for (int i = 0; i < MAXT; i++) for (int j = 0; j < MAXT; j++) toEach[i][j] = INF; }

int main() { scanf(“%d”, &cases); while (cases–) { init(); scanf(“%d%d”, &row, &col); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int tmp; scanf(“%d”, &tmp); G[i].push_back(tmp); } } scanf(“%d”, &k); for (int i = 0; i < k; i++) { scanf(“%d%d”, &target[i].x, &target[i].y); }

// 求每两个宝藏点之间的最短距离（最小代价）
for (int i = 0; i < k; i++)
{
  SPFA(i);
  for (int j = 0; j < k; j++)
  {
    // 自身到自身的代价为 0
    if (i == j) {
      toEach[i][j] = 0;
      continue;
    }
    int jx = target[j].x, jy = target[j].y;
    toEach[i][j] = min(toEach[i][j], dist[jx][jy]);
  }
  // dp[1 << i][i] 表示只访问了第 i 个点时的代价
  // 等于：从边界进来时的代价 + 自身的代价
  dp[1 << i][i] = toEdge[i] + G[target[i].x][target[i].y];
}

// solve
// 枚举从 0 到 (1 << k) - 1 的每个状态
for (int state = 0; state < (1 << k); state++)
{
  // 枚举该状态当前的终点
  for (int i = 0; i < k; i++)
  {
    // 如果状态不包含当前点，则回溯
    if ((state & (1 << i)) == 0) {
      continue;
    }

    // 如果当前状态下到终点的距离还没有计算，则回溯？
    // 不太清楚是不是这样的，因为我注释掉这段代码仍然是 AC 的
    if (dp[state][i] == INF) {
      continue;
    }

    // 枚举在当前状态时，下一个目标是去哪一个宝藏点呢
    for (int j = 0; j < k; j++)
    {
      // 如果这个宝藏点已经访问过了，就回溯，因为每个点只能走一次
      if ((state & (1 << j)) == 1) {
        continue;
      }
      // 下一个状态
      int next = (state | (1 << j));

      // 下一个状态 next，终点为 j 的最小代价等于 这个代价 和 当前代价+(cur, next)两点间最短距离 的最小值
      dp[next][j] = min(dp[next][j], dp[state][i] + toEach[i][j]);
    } // for j
  } // for i
} // for state

// 输出答案
int ans = INF;
for (int i = 0; i < k; i++)
{
  // 最终的最优答案是 min(dp[(1 << k) - 1][i]), i = 0...k
  // 因为 dp[i][j] 是以 j 为终点，但是我们最终需要从边界出去，所以还要加上终点到边界的最短距离
  ans = min(dp[(1 << k) - 1][i] + toEdge[i], ans);
}
printf("%d\n", ans);

} return 0; } ```

// EOF

文章链接： https://kirainmoe.com/blog/post/practicing-record-4th-8-20-9-10/

许可协议：CC-BY-NC-SA 4.0 国际

Yume Maruyama

まんまるお山に彩りを✨~

每周解题报告 (4th, 8/20~9/10)

13⁄200, HDU1069, Monkey and Banana

Solution

Code

14⁄200, HDU1176, 免费馅饼

Solution

Yume Maruyama

¹³⁄₂₀₀, HDU1069, Monkey and Banana

¹⁴⁄₂₀₀, HDU1176, 免费馅饼