首页 > 代码库 > 算法题--扔棋子

算法题--扔棋子

2024-07-16 10:35:14   220人阅读

题目如下：“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。“
先说下扩展：n层k个球

这道题有一个dp解，因存在递归。假设第一次扔在第r层，碎了就在1~r之间寻找，此时还剩k-1个球；没碎就在r+1~n之间寻找，还剩k个球。

代码如下：

 1 #include <iostream> 2 #include <fstream> 3 #include <sstream> 4 #include <string> 5 #include <cmath> 6 #include <iomanip> 7 #include <vector> 8 #include <deque> 9 #include <list>10 #include <queue>11 #include <stack>12 #include <map>13 #include <algorithm>14 #include <limits>15 #include <utility>16 #include <ctime>17 #include <bitset>18 using namespace std;19 20 #define MAX_FLOOR 51221 #define MAX_BALL  10022 23 int dp(int n, int k)24 {25      if(k<1 || n<1) return -1;    //错误输入26 27      if(k==1) return n-1;        //去掉一些trivial case28      if(n==1) return 0;29 30      int M[MAX_BALL][MAX_FLOOR];31      int i,j,r;32      int temp, min;33 34      for(i=0;i<=k;i++) M[i][0]=M[i][1]=0;    //F(1,k)=F(0,k)=035      for(j=2;j<=n;j++) M[1][j]=j-1;            //F(n,1)=n-136 37      /*38      状态转移方程：39      F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}40      */41      for(i=2;i<=k;i++)42          for(j=2;j<=n;j++)43          {44              min = numeric_limits<int>::max();45              for(r=1;r<=j;r++)46              {47                  temp = max(M[i-1][r], M[i][j-r])+1;48                  if(temp<min)49                      min = temp;50              }51              M[i][j] = min;52          }53 54      return M[k][n];//F(n,k)55  }56 57  int main()58  {59      int n,k;60 61      cin>>n>>k;62      cout<<dp(n, k)<<endl;63 64      return 0;65  }

这道题对于第一问还有一个解：第一个球先找出临界层所在的段，第二个球从段中找层。由于找段的次数不可避免的会增加，那么就减少每次找层的次数。（其实我没太理解）

x+(x-1)+(x-2)....

 


联系
我们