笔试算法题分享
草船借箭题目：
题目描述:
程序员小周同学这几天在看《三国演义》。今天他看到了“草船借箭”这一回，在钦佩诸葛亮巧借东风向曹操“借"箭的同
时，小周想到这么一个问题: 如果诸葛亮一共派出了N条放置草人的船来“借"箭。“悚慨”的曹操向第1条草船上射了A支
箭、第2条草船上射了B支箭，第3条草船上射的箭的数量等于前面两条船上箭的数量之和多一支，第4条草船上射的箭的
数量等于前面三条船上的箭的数量之和多一支，...，以此类推，第N条草船上箭的数量等于前面N-1条船上箭的数量之和
多一支。 下面问题来了，请问这一次诸葛亮一共从曹操那里“借”了多少支箭呢?
输入描述
输入三个正整数N、A和B，三个正整数都不超过1000，并且保证N>1，且两两之间用空格隔开。
输出描述
输出诸葛亮“借”箭的总数量。结果对1e9+7取模。
样例输入
4 1 2
样例输出
15思路：
[*]求出每条船上的箭头数量。由nums保存
a.当天箭头的数量是前面箭头数量和+1，由 preSum保存
[*]求出所有总和，即nums数组求和即可
如果写过斐波拉切数列那么本题思路就会比较明确。
#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 >> nums; long long preSum = nums + nums; 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表示考虑前i个数字，组合为j的最小的数字个数 for (int i = 0; i < n + 1; ++i) { dp = 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; im) { continue; } dp = 1;//特殊赋值 for (int j = 0; j = thisNum) { dp = min({dp,dp + 1 }); } } } if (dp == INT_MAX / 2) { cout
页:
[1]