HDU - 3281 dp
HDU DP
2023-09-27 14:26:03 时间
题意:
给你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]
代码:
1 #include <bits/stdc++.h> 2 const int maxn=1005; 3 const int INF=0x3f3f3f3f; 4 using namespace std; 5 int dp[maxn][55]; 6 int main() 7 { 8 int t; 9 scanf("%d",&t); 10 while(t--) 11 { 12 memset(dp,INF,sizeof(dp)); 13 14 int p,b,m; 15 scanf("%d%d%d",&p,&b,&m); 16 for(int i=0;i<=b;++i) 17 dp[0][i]=0; 18 for(int i=1;i<=m;++i) 19 { 20 for(int j=1;j<=b;++j) 21 { 22 for(int k=1;k<=i;++k) 23 { 24 dp[i][j]=min(dp[i][j],max(dp[i-k][j],dp[k-1][j-1])+1); 25 } 26 } 27 } 28 printf("%d %d\n",p,dp[m][b]); 29 } 30 return 0; 31 }
相关文章
- HDU 4655 Cut Pieces
- HDU 1358 Period
- 【斐波那契DP】HDU 4639——HeHe
- HDU 3046 Pleasant sheep and big big wolf(最小割)
- hdu 1022 Train Problem I
- hdu 5379 Mahjong tree(树形dp)
- hdu 1827 Summer Holiday tarjan+缩点
- Hdu 2159 FATE dp
- LianLianKan HDU - 4272 状压dp
- HDU 4833 Best Financing (DP)
- HDU 4585 Shaolin(水题,STL)
- Big Event in HDU(dp算法)
- [ACM] HDU 2255 奔小康赚大钱 (二分图最大权匹配,KM算法)
- HDU 4927 Series 1
- [ACM] hdu 4405 Aeroplane chess (概率DP)
- HDU ACM 2845 Beans->动态规划
- hdu 2082 生成函数
- 2019 杭电多校第八场 HDU - 6665 Calabash and Landlord 两矩形分平面