A33808. 猴子拿桃
填空题
困难
知识点
题目描述
猴子拿桃
题目描述
有N筐桃子从左到右排成一排，已知每筐桃子的数量。现猴子要按照以下规则拿取桃子：
1）猴子每次拿一筐桃子，一共要拿K次桃子；
2）猴子只能按照从左到右的顺序拿取桃子，不能回头，且每次拿取桃子的数量不能少于（大于等于）上一次。
当给定桃子筐数N（1≤N≤12）及每筐桃子的数量，和要拿取桃子的次数K（1≤K≤N），请编写程序，如果有符合规则的拿取方式，输出猴子最多可以拿到的桃子数量，否则输出0。
例如：
N = 4，4筐桃子的数量从左到右依次为16，12，16，17；
K=3，猴子一共要拿3次桃子，符合规则的拿取方式有：[16,16,17]，[12,16,17]；
其中可拿取到最多桃子的方式是：[16,16,17]，合计为49。则猴子最多可以拿到49个桃子。
输入描述
第一行输入两个正整数N和K（1≤N≤12，1≤K≤N），分别表示桃子的筐数和一共要拿取桃子的次数，正整数之间以一个空格隔开
第二行输入N个正整数（10≤正整数≤200），从左到右依次表示每筐桃子的数量，正整数之间以一个空格隔开
输出描述
输出一个整数，如果有符合规则的拿去方式，输出猴子最多可以拿到的桃子数量，否则输出0
样例输入
4 3
16 12 16 17
样例输出
49
参考答案
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int a[N + 1];
bool vis[N + 1];
int f[N + 1];
int maxs = 0;
bool hasr = false;
void output(int k) {
for(int i = 1; i <= k; i++) {
cout << f[i] << ' ';
}
cout << endl;
}
void dfs(int n, int k, int lstp, int t, int s) {
int maxsum = 0;
if (t > k) {
if (s > maxs)
maxs = s;
hasr = true;
return;
}
for (int i = lstp + 1; i <= n; i++) {
if(a[i] < a[lstp]) // 下降，跳过
continue;
if(vis[i]) // 已选，跳过
continue;
vis[i] = true;
f[t] = a[i];
dfs(n, k, i, t + 1, s + a[i]);
f[t] = 0;
vis[i] = false;
}
return;
}
int main() {
int n, k;
int f = false;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs(n, k, 0, 1, 0);
if(hasr)
cout << maxs;
else
cout << 0;
return 0;
}
上一题
下一题