题意:
给你 b 个球, m 个楼层, 你需要找到一个楼层数 k, 使得从小于 k 这个楼层上面扔下去球, 而球不会碎. 求在最糟糕的情况下你最多要尝试多少次
题解:
dp[i][j]表示你有 b 个球, 楼层总数为 m, 你找到那个 k 一共尝试了 dp[i][j]才找到
如果在某楼层 x 下扔下球, 球碎了, 那么 dp[i][j]状态可转化为 dp[x-1][j-1] , 因为球碎了, 那么证明我们要找的那个 k 就在 [1,x] 这个集合里面, 又因为让你求最糟糕情况下你要尝试多少次, 那么 x 就不会是那个我们找的 k
如果在某楼层 x 下扔下球, 球没碎, 那么 dp[i][j]状态可转化为 dp[m-x][j]
代码:
- #include <bits/stdc++.h>
- const int maxn=1005;
- const int INF=0x3f3f3f3f;
- using namespace std;
- int dp[maxn][55];
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- memset(dp,INF,sizeof(dp));
- int p,b,m;
- scanf("%d%d%d",&p,&b,&m);
- for(int i=0;i<=b;++i)
- dp[0][i]=0;
- for(int i=1;i<=m;++i)
- {
- for(int j=1;j<=b;++j)
- {
- for(int k=1;k<=i;++k)
- {
- dp[i][j]=min(dp[i][j],max(dp[i-k][j],dp[k-1][j-1])+1);
- }
- }
- }
- printf("%d %d\n",p,dp[m][b]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3528462.html