陌

用户名：lzy599

访问量：6584

签　名：

哪有什么签名

等　　级
排　　名	554
经　　验	4218
参赛次数	14
文章发表	12
年　　龄	0
在职情况	学生
学　　校	福建农林大学东方学院
专　　业

　　自我简介：

TA的其他文章

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）
浏览：598

[传智杯]众数出现的次数-题解(C++代码)（简短+易懂）
浏览：305

蓝桥杯2019年第十届真题-完全二叉树的权值-题解(C++代码)（前缀和+简短 +图解）
浏览：883

你可能喜欢

决战拼接-题解(C++代码)（超详细。。应该很详细了）

　　作者: 陌　　　　发表时间：2020-03-24 20:46:08 浏览：740　|　评论：0　

原题链接：决战拼接

# 决战拼接

## 题目链接：

[https://www.dotcpp.com/oj/problem2112.html](https://www.dotcpp.com/oj/problem2112.html)

## 题目简介：

### 题目描述

> 终于到了大决战的时刻了，杰洛特和狂猎在野外各自带兵开展大战。
> 狂猎则派出一员大将，而杰洛特需要派出相应的部队进行迎敌。
> 现规定：
> 给出规定的部队给杰洛特，每一只部队有相应的战斗力，杰洛特派出至少一只部队迎战狂猎。(假设战斗力相等的部队数量无限)
> 为了公平，狂猎也派出战斗力一定值的大将进行迎战，狂猎派出大将的战斗力需要与杰洛特派出的部队战斗力相等
> 请告诉杰洛特，派出最少的部队数去迎战狂猎的大将(为了避免牺牲嘛)

### 输入

> 第一行一个n表示杰洛特可派选的部队
> 接下来一行共n个数字，每一个数字表示部队战斗力

在接下来一行一个m表示狂猎派出的大将的战斗力

n,m不会超过整型最大范围

### 输出

> 请输出杰洛特派出的最少的部队数，如果不符合要求，则输出-1表示拒绝作战

### 样例输入

```
3
1 2 5
11
```

### 样例输出

```
3
```

## 思路分析：

这个可以使用动态规划来解决。

- 题目意思大概就是给你一个数，并告诉你可以用哪些数来凑，然后怎么凑能刚好凑到这个数并且凑的次数要最少的。

- 如例题有：1   2    5

![image-20200324200642305](https://images.21hut.com/typora/20200324200643-203888.png)

可以发现无论是以哪种方式到达11，最后的结果都会在每种情况上+1，那么影响最后结果的就是拼凑成6的次数，以及拼凑成9，10的次数，当然我们这里要认为他们拼凑的方案是最优解，然后比较谁更少，再加上1，就是最后的结果了。

![image-20200324202251470](https://images.21hut.com/typora/20200324202252-40462.png)

**我们都相信，如果dp[6]或者9和10拼凑成他们的方案是最优解，那么再最后加上1，得到的DP[11] 也是最优解。**

> 这个应该好理解，就是如果拼凑成6的那个方案是所有方案中最优的那一个，那么再加上1（6拼凑到10的最优方案）最后会得到拼凑11的方案也是最优的方案。**毋庸置疑，两个最优的方案放到一起最后的结果也是最优的**

**那么问题又来了，拼凑成6的最优解释什么呢？同样我们可以使用相同的方法：**

![image-20200324203203894](https://images.21hut.com/typora/20200324203204-980409.png)

那么我们可以得到拼凑成6的三种情况，依次类推。

因为这个例题给我们三个可拼凑的数：1、2、5，所以我们可以轻易得知，拼凑成1、2、5的最优解就是用他们自身，所以最优的解就是只需要拼凑一次。所以DP[1] = DP[2] = DP[5] = 1;这是**基础解**

我们可以得出**递推公式**：DP[i] = min(DP[i],DP[i-1],DP[i-2],DP[i-5])

当然这边的1、2、5是随着题目改变而改变的。

不知道有没有理清楚，为代码加了注释，结合看会好一点！

可食用：

![image-20200324195553132](https://images.21hut.com/typora/20200324195554-466387.png)

## 代码展示：

``` cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<limits.h>
using namespace std;

int main(){
    int n,m;
    cin>>n;
    int arr[n];
    int max = 0;
    for(int i = 0; i< n; i++){
        cin>>arr[i];
        if(arr[i] > max)
        max = arr[i];
    }
    cin>>m;
    //定义一个数组存储，每个数的最优解
    int dp[m+1];
    //赋初值
    for(int i=0; i<= m; i++) dp[i] = INT_MAX;
    //以下的不用推导的基础解，就是一眼就可以看出来的最优解
    dp[0] = 0;
    for( int i = 0; i  < n; i++){
        if(arr[i]<m)
        dp[arr[i]] = 1;
    }
    //进行递推
    for( int i = 1; i <= m; i++){
        	//对题目所给的可拼凑的数进行遍历，看哪种情况更优
            for(int j = 0; j < n; j++)
                if(i-arr[j] >= 0 && dp[i-arr[j]] != INT_MAX)
                    //取三种情况中最小的那个
                dp[i] =min(dp[i],dp[i-arr[j]] + 1);
            } 
    //输出
    if(dp[m]<INT_MAX) cout<<dp[m]<<endl;
    else cout<<-1<<endl;

return 0;
}
```

0.0分

14 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

陌

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

汽水瓶（C++代码）（直接n/2就可以了）

决战拼接-题解(C++代码)（超详细。。应该很详细了）

评论区

精彩推荐

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

分糖果（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1128题解（返回值为数组的情况）

陌

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

汽水瓶 （C++代码）（直接n/2就可以了）

决战拼接-题解(C++代码)（超详细。。应该很详细了）

评论区

精彩推荐

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

分糖果 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1128题解（返回值为数组的情况）

上车人数（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

　　评论区

分糖果（C++代码）

WU-拆分位数（C++代码）