题目大意:给你n个规格一样的气球和一栋大楼的高度,求最少试验几次能测出气球最高在哪一层掉下来不破。
如果这道题想用(dp[i][j]=用i个气球测出j高度的楼需要几次)来作为状态的话,那你就输了,因为楼的高度太大了。
正确的做法是用(dp[i][j]=用i个气球测j次最高能测出多高的楼)来作为状态。假设你现在手里有i个球,要求测j次,最高能测出h层来,你在第k层楼上测,如果球破了,那么你手里还剩下i-1个球,则问题转化成了(用i-1个球测j-1次测出k-1层以下的楼);如果球没破,那么你手里依旧有i个球,则问题转化成了用(i个球测j-1次测出k层以上的楼),由于不确定球是否会破,所以两个任务都必须能够完成,因此能测出的最大高度为$dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1$,+1是因为你在第k层测了一次以后,第k层就已经废掉了,不用再测了,因此可以把第k层作为“多出来的那一层”。
有点逆向思维的感觉。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 const int N=100+10; 5 ll dp[N][N]; 6 int n; 7 ll h; 8 9 int main() { 10 for(int i=1; i<N; ++i) 11 for(int j=1; j<N; ++j) 12 dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1; 13 while(scanf("%d%llu",&n,&h)&&n) { 14 int i; 15 for(i=0; i<=63; ++i)if(dp[n][i]>=h)break; 16 if(i==64)printf("More than 63 trials needed. "); 17 else printf("%d ",i); 18 } 19 return 0; 20 }