T1-E 星际飞船

2023-09-05 阅读 28 评论 0

摘要：题目描述：现有一星际飞船要从A地到达B地，两地距离为m，飞船配备n个引擎，每个引擎具有启动其一次能前进的距离a[i]，（引擎可以重复使用），请问到达目的地启动最少的引擎次数是多少？（数据保证题目有解

题目描述：

现有一星际飞船要从A地到达B地，两地距离为m，飞船配备n个引擎，每个引擎具有启动其一次能前进的距离a[i]，（引擎可以重复使用），请问到达目的地启动最少的引擎次数是多少？（数据保证题目有解）

乍一看很像贪心，然而之前c3_a就是类似的问题，却需要用01背包求解，

（如果不清楚什么是背包问题，移步(38条消息) 背包九讲——全篇详细理解与代码实现_良月澪二的博客-CSDN博客_背包九讲）

这个题不同点在于引擎可以重复使用，即为完全背包问题，只不过收益的最大值转变为个数的最小值，状态转移方程如下

$f(i,j)=min(f(i-1,j),f(i-1,j-a[i])+1)$

用一维数组优化

for(int i=1;i<=n;i++){for(int j=a[i];j<=m;j++){dp[j]=min(dp[j], dp[j-a[i]]+1);}}

还需注意的是，由于本题dp数组代表的是引擎个数的最小值，所以数组需要初始化如下

for(int j=1;j<=m;j++) dp[j]=INT_MAX/2;dp[0]=0;

最后输出dp[m]即可得到答案