ToB企服应用市场:ToB评测及商务社交产业平台

标题: 笔试算法题分享 [打印本页]
作者: 铁佛    时间: 2023-11-3 14:03
标题: 笔试算法题分享
草船借箭

题目：
  1. 题目描述:
  2. 程序员小周同学这几天在看《三国演义》。今天他看到了“草船借箭”这一回，在钦佩诸葛亮巧借东风向曹操“借"箭的同
  3. 时，小周想到这么一个问题: 如果诸葛亮一共派出了N条放置草人的船来“借"箭。“悚慨”的曹操向第1条草船上射了A支
  4. 箭、第2条草船上射了B支箭，第3条草船上射的箭的数量等于前面两条船上箭的数量之和多一支，第4条草船上射的箭的
  5. 数量等于前面三条船上的箭的数量之和多一支，...，以此类推，第N条草船上箭的数量等于前面N-1条船上箭的数量之和
  6. 多一支。 下面问题来了，请问这一次诸葛亮一共从曹操那里“借”了多少支箭呢?
  7. 输入描述
  8. 输入三个正整数N、A和B，三个正整数都不超过1000，并且保证N>1，且两两之间用空格隔开。
  9. 输出描述
  10. 输出诸葛亮“借”箭的总数量。结果对1e9+7取模。
  11. 样例输入
  12. 4 1 2
  13. 样例输出
  14. 15
复制代码
思路：
​        a.当天箭头的数量是前面箭头数量和+1，由 preSum保存
如果写过斐波拉切数列那么本题思路就会比较明确。
[code]#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() {    long long mod = 1e9 + 7;    int n = -1; cin >> n;    vector nums(n,0);    cin >> nums[0] >> nums[1];    long long preSum = nums[0] + nums[1];    for (int i = 2; i < n; ++i) {        nums = (preSum + 1)%mod;        preSum += nums;        preSum %= mod;    }    long long res = 0;    for (int i = 0; i < nums.size(); ++i) {        res += nums;        res %= mod;    }    cout > m;    vector dp(n + 1, vector(m+10, INT_MAX/2));//dp[j]表示考虑前i个数字，组合为j的最小的数字个数    for (int i = 0; i < n + 1; ++i) {        dp[0] = 0;//任何组合组成0 需要的个数是0个    }    vector numsVt;    for (int i = 0; i < n; ++i) {        int t = -1; cin >> t;        numsVt.push_back(t);    }    for (int i = 1; i  m) { continue; }        dp[thisNum] = 1;  //特殊赋值                for (int j = 0; j = thisNum) {                dp[j] = min({dp[j],dp[i - 1][j - thisNum] + 1 });            }        }    }    if (dp[n][m] == INT_MAX / 2) {        cout



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4