我正在解决一个关于数组的基本问题。问题陈述如下:
SIS开了一个篮球场,所以Demid决定举行篮球练习课。有2⋅n名学生来参加Demid的练习课,他将这些学生排成两行相同大小的队伍(每一行恰好有n个人)。学生在每一行中按照从左到右的顺序编号为1到n。
现在,Demid想选择一个队伍打篮球。他将从左到右选择球员,并且除了第一个选中的球员之外,每个选中球员的索引都严格大于上一个选中球员的索引。为了避免偏袒其中一个队伍,Demid会这样选择学生,使得没有连续的已选学生属于同一行。第一个学生可以从所有2n个学生中选择(没有其他限制),并且团队可以由任意数量的学生组成。
为了组成一支完美的队伍,Demid认为他应该选择这样的学生,即所有被选择学生的身高总和最大。帮助Demid找到可以选择的团队中身高总和最大的球员。
例如,如果输入是:(第一行包含n的值,接下来跟随两行,包含学生的身高)
5
9 3 5 7 3
5 8 1 4 5
我的处理方式是:
#These are global variables and functions.
int arr1[n],arr2[n],sum=0,max=0;
void func1(i)
{
if(i==n)
{
if(sum>max)
max=sum;
return;
}
sum+=arr1[i];
for(k=i+1;k<n;k++)
func2(k);
}
void func2(i)
{
if(i==n)
{
if(sum>max)
max=sum;
return;
}
sum+=arr2[i];
for(k=i+1;k<n;k++)
func1(k);
}
#Caller module. In main
for(i=0;i<n;i++)
{
sum=0;
func1(i);
}
这是我的算法,基于我的逻辑推理。我还没有编写代码,稍后会编写。因此请随意指出代码中的任何逻辑错误。 我知道这可以使用动态规划方法轻松解决,而这个算法并不是那样的。在这种情况下,函数将是什么样子? 就我所知,这个算法中的问题是我需要全局声明
arr1
和arr2
,而我在主函数中获得n的值。
int arr1[n],arr2[n]
-- 如果n
是一个变量,这不是有效的 C++。 - PaulMcKenzie