标签：URAL 动态规划

题目链接

题目大意

给定比较硬的鹰蛋个数eggs， 和楼层数floors，问最差情况下的实验次数为多少时，才能确定蛋刚好不破裂的那一层？

思路^[1]

建立动态规划函数g(trail, eggs)， 表示eggs个蛋实验trail次最差情况下能确定最大的层数。
明显，只给一个蛋的时候只能逐层往上实验，g(trail, 1) = trail;
只实验一次只能确定一层，g(1, eggs) = 1。

那么，进行一次实验，情况有二：
蛋碎了，用剩下的eggs-1个蛋进行剩下的trial-1次实验能最高层数为g(trial-1, eggs-1);
蛋没碎，用eggs个蛋进行剩下的trial-1次实验能最高层数为g(trial-1, eggs);

故g(trial, eggs) = g(trial-1, eggs-1) + g(trial-1, eggs) + 1.

代码

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
#include <cstdio>

#define MAX 1000

int g(int eggs, int floors);

int main() {
  int eggs, floors;
  while (scanf("%d %d", &eggs, &floors) != EOF && (eggs && floors)) {
    printf("%d\n", g(eggs, floors));
  }

  return 0;
}

int g(int eggs, int floors) {
  int matrix[MAX + 5][MAX + 5] = { 0 };
  for (int i = 0; i <= MAX; i++) {
    matrix[1][i] = 1;
    matrix[i][1] = i;
  }

  if (eggs == 1) return floors;
  if (floors == 1) return 1;
  for (int trial = 1; trial <= floors; trial++) {
    for (int egg = 1; egg <= eggs; egg++) {
      if (trial > 1 && egg > 1) {
        matrix[trial][egg] = matrix[trial - 1][egg - 1] + matrix[trial - 1][egg] + 1;
        if (matrix[trial][egg] >= floors && matrix[trial-1][egg] < floors)
          return trial;
      }
    }
  }
}

优化

数据规模不大，源代码重复建表，但是这个表只是不同的数据组合搜索出来的位置不同，表格内容是完全一样的， 故将建表操作放在搜索结果前面。

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
#include <cstdio>

#define MAX 1000

int g(int eggs, int floors);

int main() {
  int eggs, floors;
  while (scanf("%d %d", &eggs, &floors) != EOF && (eggs && floors)) {
    printf("%d\n", g(eggs, floors));
  }

  return 0;
}

int g(int eggs, int floors) {
  int matrix[MAX + 5][MAX + 5] = { 0 };
  for (int i = 0; i <= MAX; i++) {
    matrix[1][i] = 1;
    matrix[i][1] = i;
  }

  if (eggs == 1) return floors;
  if (floors == 1) return 1;
  for (int trial = 1; trial <= floors; trial++) {
    for (int egg = 1; egg <= eggs; egg++) {
      if (trial > 1 && egg > 1) {
        matrix[trial][egg] = matrix[trial - 1][egg - 1] + matrix[trial - 1][egg] + 1;
        if (matrix[trial][egg] >= floors && matrix[trial-1][egg] < floors)
          return trial;
      }
    }
  }
}

1. 参考 朱晨光《从《鹰蛋》一题浅析对动态规划算法的优化》 ↩