Ural 1223.Chernobyl’ Eagle on a Roof

  题目的大意是有x（1<=x<=1000)个强度相同的蛋，有一座有y（1<=y<=1000)层的楼，蛋的强度为E（0<=E<=y),在i层把蛋扔下楼，若E

 很裸的动归题，最容易想的就是开个二维数组，dp[x][y]表示用x个蛋在y层楼高的楼测试最坏情况下至少需要

dp[x][y]次测试。状态转移是如果在第i层扔蛋，碎的话说明E=i，变成求

1+dp[x][y-i]，由于是最坏情况，所以取两者的较大者作为在第i层扔蛋所需的测试总数，由于要求最小值，那就对每层都做同样的计算取最小者。这里使用记忆化搜索会比较简便。

 但是第一个案例就TLE了，原因是这是O（n^3）的算法，1000的3次方肯定超时。然后这时发现，因为假设情况最坏，所以每次测试缩小的范围都会尽可能小，那么要最快测试完就是二分地测试，1000至多需要10次就能结束，所以当蛋数目超过10跟只有10个的结果是一样的，所以开的dp数组可以缩小至11*1001，在记忆化搜索中当y>10时返回y=10的结果即可。这就把复杂度压缩到O（n^2）.

#include 
#include 
using namespace std;
int dp[15][1001];
int d(int a, int b)
{if (a > 11)return d(11, b);if (dp[a][b] != -1)return dp[a][b];if (a == 1)return dp[a][b] = b;if (b == 0)return dp[a][b] = 0;for (int i = 1;i <= b;i++){int temp = 1 + d(a - 1, i - 1) > 1 + d(a, b - i) ? 1 + d(a - 1, i - 1) : 1 + d(a, b - i);if (dp[a][b] == -1 || dp[a][b] > temp)dp[a][b] = temp;}return dp[a][b];
}
int main()
{memset(dp, -1, sizeof(dp));while (1){int a, b;cin >> a >> b;if (a == 0 && b == 0)break;cout << d(a, b) << endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！