p2669 [noip2015 普及组] 金币
时间: 2023-04-25 22:03:43 浏览: 103
题目描述
有 n 个金矿,第 i 个金矿可开采出金子的数量为 g[i],需要的工人数为 p[i]。有 m 个工人,每个工人只能开采一个金矿,每个金矿最多只能开采一次。
现在需要你编写一个程序,计算出在不超过 m 个工人的情况下,最多可以获得多少金子。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示每个金矿可开采出的金子数量 g[i]。
第三行包含 n 个整数,表示每个金矿需要的工人数 p[i]。
输出格式
输出一个整数,表示在不超过 m 个工人的情况下,最多可以获得多少金子。
输入样例
5 10
400 500 200 300 350
5 5 3 4 3
输出样例
900
数据范围
1≤n≤1000,1≤m≤10000,0≤g[i],p[i]≤1000
解题思路:
采用动态规划的方式解决。定义状态f(i,j)表示对前i个金矿,用j个工人最多可获得的金子数。
则转移方程为f(i,j)=max{f(i-1,j),f(i-1,j-p[i])+g[i]}
其中f(i-1,j)表示不选择第i个金矿,f(i-1,j-p[i])+g[i]表示选择第i个金矿。
边界条件为f(i,0)=0,f(0,j)=0。
最终答案为f(n,m)。
时间复杂度分析:
共有n*m个状态,每个状态都需要进行一次状态转移,则总时间复杂度为O(nm)。
参考代码:
相关问题
noip2015普及组初赛解析
noip2015普及组初赛解析主要是对该比赛的初赛环节进行解析和评估。该比赛是全国青少年信息学竞赛的一部分,旨在选拔和培养优秀的信息学人才。
初赛解析主要包括对题目难度、题型、内容以及解题思路的分析。通过对比赛题目的解析,可以了解该比赛的难易程度、与往年的对比,以及参赛选手的竞赛水平。
在分析题目难度和题型时,可以看到题目可能分为编程题、算法题、逻辑题等,这些题目的难度可能因题目内容而异。对于初学者来说,可能需要花更多的时间和精力来解决较难的题目。而对于有经验的选手来说,可能能迅速找到解题思路和解决方案。
在解析过程中还会讨论各题目的解题思路和解题技巧。这些思路和技巧可以帮助选手更好地解决类似的问题,提高编程能力和解题能力。
除了题目的分析,初赛解析还可能会讨论参赛选手的表现和竞赛状况。对于那些优秀的选手,他们可能能够在短时间内解决多个题目,并且得到较高的得分。而对于一些初学者来说,可能需要更多的训练和实践才能提高。
总之,noip2015普及组初赛解析旨在提供对该比赛的评估和反思,帮助选手和教练了解比赛的难度和水平,并为今后的竞赛提供参考。它也是选手提高编程能力和解题能力的一个重要途径。
P2669 [NOIP2015 普及组] 金币 提交 206.05k 通过 116.36k 时间限制 1.00s 内存限制 125.00MB 提交答案 加入题单
题目描述
有 $n$ 个硬币排成一个环,第 $i$ 个硬币有价值 $a_i$ ,其中 $1\le i\le n$。你可以选择一个硬币 $i$ ,同时拿走硬币 $i-1$ 和 $i+1$ (如果存在),然后得到 $a_i$ 的价值。
重复上述操作,直至只剩下一个硬币。请问最多能得到多少价值?
输入格式
第一行包含一个整数 $n$ ,表示硬币的数量。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$,表示每个硬币的价值。
输出格式
输出一个整数,表示最多能得到的价值。
数据范围
$1\leqslant n\leqslant10^5$,$1\leqslant a_i\leqslant10^4$
输入样例:
3
1 2 3
输出样例:
3
算法1
(模拟) $O(n^2)$
由于硬币是排成一个环的,所以我们将第一个硬币和最后一个硬币连成一个环,然后处理两种不同的情况:
- 拿走第 $i$ 个硬币,同时拿走 $i-1$ 和 $i+1$,然后将整个环缩小为 $n-3$ 个硬币;
- 拿走第 $i$ 个硬币,同时拿走 $i-1$ 和 $i+1$,然后将整个环缩小为 $n-2$ 个硬币。
在这两种情况中选择一个最优的即可。
时间复杂度
$O(n^2)$,其中 $n$ 是硬币的数量。
C++ 代码
算法2
(动态规划) $O(n^2)$
由于硬币是排成一个环的,所以我们将第一个硬币和最后一个硬币连成一个环,然后设 $f[i][j]$ 表示处理前 $i$ 个硬币,已经拿走了 $j$ 个硬币,所能得到的最大价值,则状态转移方程如下:
$$
f[i][j]=\max\left\{
\begin{aligned}
f[i-2][j-1]+a[i] && (i\ge2\ \&\&\ j\ge1) \\
f[i-1][j] && (i\ge1\ \&\&\ j\ge0)
\end{aligned}
\right.
$$
时间复杂度
$O(n^2)$,其中 $n$ 是硬币的数量。
C++ 代码
算法3
(动态规划) $O(n)$
观察上面的状态转移方程,我们发现 $f[i][j]$ 只依赖于 $f[i-2][j-1]$ 和 $f[i-1][j]$,因此我们可以使用滚动数组来优化空间复杂度。
时间复杂度
$O(n)$,其中 $n$ 是硬币的数量。
C++ 代码