蓝桥杯练习题J

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=9

题目描述
【问题描述】 某公司生产长钢管,然后一般,会将钢条切断,变成不同长度,然后去售卖。其中有个问题是,不同长度的钢管的售价是不一样的,但是它们并不是完全按照比例来,比如2米的钢管售价要比3米的钢管售价要少,但是并不是2比3的比例。例如钢管的长度售价表如下: 长度i 1 2 3 4 5 6 7 8 9 10 价格Pi 1 5 8 9 10 17 17 20 24 30 于是问题就来了,比如10米以内的钢管,要如何切割,切割成多长的几条,才能让售价最高?
输入
输入的数据为11个正整数,1-10个正整数代表Pi,即长度为i的钢管价格,第11个正整数N代表要切割的钢管长度。
输出
输出最高售价。结尾加一换行符。

1
2
3
4
样例输入
1 5 8 9 10 17 17 20 24 30 9
样例输出
25

思路:
穷举,把所有的可能都计算出来,最大值就出来了..
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int a[10];
int max1=0;
int n;
void select(int j,int now,int sum){
if(now>max1&&sum<=n){
max1=now;
}
if(sum>n)return;
sum=sum+j+1;
now=now+a[j];
for(int i=0;i<10;i++){
select(i,now,sum);
}
}
int selectmain(){
for(int i=0;i<10;i++){
select(i,0,0);
}
}
main(int argc, char** argv) {
for(int i=0;i<10;i++){
cin>>a[i];
}
cin>>n;
selectmain();

cout << max1 <<endl;
return 0;
}