YumeのDiary

6 年間、共に歩んでくれたあなたへ。

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

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

9月 10日, 2017

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

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

13/200, 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;
}

14/200, HDU1176, 免费馅饼

Solution

这题有两种做法。

  1. 第一种是直接 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 存在)

  2. 数塔做法:联想一下数字三角形,从下往上递推回去就行了。dp[i][j] 还是表示第 i 秒在第 j 个位置能取到的最大值,不同的是要逆推,并且可以直接覆盖掉之前的值(因为计算完就没有用了),则:
    dp[i][j] = max(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + dp[i][j]

Code

// Solution 1
#include <bits/stdc++.h>
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;
}
// Solution 2
#include <bits/stdc++.h> 
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

// Solution 1: O(n^2)
#include <bits/stdc++.h> 
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;
}
// Solution 2: O(n)
#include <bits/stdc++.h>
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

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

#include <bits/stdc++.h> 
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

#include <bits/stdc++.h>
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<int> 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<Point> 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

· · ·

Yume Kankawa


Use Disqus
Use Gitment (境内用户推荐)