UVa10934 装满水的气球

原题链接：UVa10934

解析：设还剩i个气球，j次机会时能够测得的最大高度为d[i][j]（换句话说，就是d[i][j]层内，可以用i个气球j次机会测出气球硬度为j），可以知道：

• 如果此层气球炸了，那么就意味着d[i][j] - 1 层必须用i-1个气球，测试j-1次测出来，于是d[i][j] = d[i-1][j-1] + 1。
• 如果此层没有破裂，那么说明还有i个气球，j-1次机会来在d[i][j]的基础上测最高层数，因此d[i][j] = d[i-1][j-1]+1+d[i][j-1]

代码实例：

#include<iostream>
#include<cstring>
using namespace std;

const int maxk = 100;
const int maxa = 63;

unsigned long long d[maxk+1][maxa+1];

int main() {
  memset(d, 0, sizeof(d));
  for(int i = 1; i <= maxk; i++)
    for(int j = 1; j <= maxa; j++)
      d[i][j] = d[i-1][j-1] + 1 + d[i][j-1];

  int k;
  unsigned long long n;
  while(cin >> k >> n && k) {
    int ans = -1;
    for(int i = 1; i <= maxa; i++)
      if(d[k][i] >= n) { ans = i; break; }
    if(ans < 0) cout << "More than " << maxa << " trials needed.
";
    else cout << ans << "
";
  }
  return 0;
}