poj3783 Balls
題意：
?有一些雞蛋，我們現在想知道這些雞蛋的硬度，然后現在有一座很高很高的大樓里，我們現在要在這座大樓上測驗雞蛋的硬度，每個雞蛋的硬度相同，雞蛋的硬度定義為：如果雞蛋從第 m 層上掉下來沒有破裂，而從第 m+1 層上掉下來就破裂了，那么這個雞蛋的硬度就是 m ，某個雞蛋如果在實驗中破裂了就永遠的損失了，我們現在有 n 個雞蛋，那么在最壞情況下我們最少需要做多少次實驗呢？
思路：
? 這是一個很經典的dp問題，設dp[n,m]是第i層樓，有k個雞蛋時找到符合條件的最少測驗次數
則一個雞蛋從第 i 層扔下，如果碎了，還剩 m?1 個雞蛋，為確定下面樓層中的安全位置，還需要dp[i?1,m?1] 次（子問題）；不碎的話，上面還有 n?i 層，還需要 dp[n?i,m]次（子問題，物體 n 層樓的上 n?i 層需要的最少判斷次數和物體 n?i 層樓需要的最少判斷次數其實是一樣的）
這里因為是要找最壞情況的最優解
所以在遍歷每層樓的時候，應該要選擇每一層樓中兩種情況的最大值，然后再去比較其中的最小值
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#define __int128 LL
using namespace std;
typedef long long ll;
const int mod = 1e9;
const int maxn = 1e3 + 5;
const int INF = 1e9 + 7;
int dp[maxn][60];//dp[i][j]:表示在 i 層樓 還有 j 個雞蛋的最小判斷次數
void DP(int n,int m)
{
memset(dp,0,sizeof dp);
//對于一個雞蛋，只能一層一層的試
for(int i = 1; i <= n; i++){
dp[i][1] = i;
}
//對于只有一層,肯定有且僅有一次
for(int i = 1; i <=m; i++){
dp[1][i] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 2; j <= m; j++){
dp[i][j] = i;//初始最壞結果是i次
for(int k = 1; k <= i; k++) dp[i][j] = min(dp[i][j] ,max(dp[k - 1][j - 1] + 1,dp[i - k][j] + 1));
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
int op,n,m;
cin>>op>>m>>n;
DP(n,m);
cout<<op<<' '<<dp[n][m]<<endl;
}
return 0;
}```
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198659.html
標籤：其他
上一篇：設計模式中的其中一種-單例模式
下一篇：解決懶漢式執行緒安全問題