猿宝最近在玩一个猜数字游戏,给定一个数字n, 表示答案在1到n之间,每次可以猜一个数字,猜中游戏胜利,但如果猜错了,将要花费所猜数字的金币,并得知是猜大了还是猜小了,但是有k次机会可以免除此花费 。猿宝 想知道,至少需要准备多少金币能确保获得游戏胜利。-笔试面试资料

这是qklbishe.com第14653 篇笔试面试资料
提供答案分析,通过本文《猿宝最近在玩一个猜数字游戏,给定一个数字n, 表示答案在1到n之间,每次可以猜一个数字,猜中游戏胜利,但如果猜错了,将要花费所猜数字的金币,并得知是猜大了还是猜小了,但是有k次机会可以免除此花费 。猿宝 想知道,至少需要准备多少金币能确保获得游戏胜利。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

猿宝最近在玩一个猜数字游戏,给定一个数字n,表示答案在1到n之间,每次可以猜一个数字,猜中游戏胜利,但如果猜错了,将要花费所猜数字的金币,并得知是猜大了还是猜小了,但是有k次机会可以免除此花费猿宝想知道,至少需要准备多少金币能确保获得游戏胜利。

猿宝最近在玩一个猜数字游戏,给定一个数字n,  表示答案在1到n之间,每次可以猜一个数字,猜中游戏胜利,但如果猜错了,将要花费所猜数字的金币,并得知是猜大了还是猜小了,但是有k次机会可以免除此花费 。猿宝 想知道,至少需要准备多少金币能确保获得游戏胜利。 JCoder
区间DP,转移的时候注意子问题分为用了机会和没用机会
#include <bits/stdc++.h> using namespace std;  int n, m, dp[305][305][25]; int main() {     scanf("%d%d", &n, &m);     for (int i = 1; i <= n; i++) {         for (int j = 0; j <= m; j++) {             dp[i][i][j] = 0;             dp[i][i - 1][j] = 0;         }     }     for (int t = 0; t <= m; t++) { //用了几次机会         for (int i = n; i >= 1; i--) { //L             for (int j = i + 1; j <= n; j++) { //R                 dp[i][j][t] = 0x3f3f3f3f;                 for (int k = i; k <= j; k++) { //猜k                     int tmp1 = max(dp[i][k - 1][t], dp[k + 1][j][t]) + k;                     dp[i][j][t] = min(dp[i][j][t], tmp1);                     if (t) {                         int tmp2 = max(dp[i][k - 1][t - 1], dp[k + 1][j][t - 1]);                         dp[i][j][t] = min(dp[i][j][t], tmp2);                     }                                      }             }         }     }     printf("%dn", dp[1][n][m]);      return 0; } 

今天 13:23:28 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 猿宝最近在玩一个猜数字游戏,给定一个数字n, 表示答案在1到n之间,每次可以猜一个数字,猜中游戏胜利,但如果猜错了,将要花费所猜数字的金币,并得知是猜大了还是猜小了,但是有k次机会可以免除此花费 。猿宝 想知道,至少需要准备多少金币能确保获得游戏胜利。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情