合唱团

 

题目描述

有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个 整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积。

示例1

输入

37 4 72 50

输出

49

 

分析：这道题用动态规划实现，因为存在最优子结构性质。

问题分解：分解是关键，设f(n,k)表示先从n个人里选择最后一个人，然后再从剩下的n-1个人里选择k-1个人，并且让这一个和前面的k-1个满足约束条件

数学描述【找到递归式】：a[end]>0 f(end,k)=max{f(then,k-1)}*a[end]}    (max(k-1,end-d)=<then<=end-1)      

　　　　　　　　　　　   a[end]<0 f(end,k)=max{g(then,k-1)}*a[end]}    (max(k-1,end-d)=<then<=end-1)       //因为能力值有负值，所以多加一个数组g[][]用来保存乘积最小值

 

递归式转化：

f(end,k)=max{f(then,k-1)*a[end],g(then,k-1)*a[end]    (max(k-1,end-d)=<then<=end-1)

g(end,k)=min{f(then,k-1)*a[end],g(then,k-1)*a[end]    (max(k-1,end-d)=<then<=end-1)

 

 

注意事项：这道题的值要用long类型保存。

我的代码实现：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N 100 5 int a[N]; 6 long f[N][N],g[N][N]; 7  8 int max1(int a,int b){ 9     return a>b?a:b;10 }11 12 long max(long a,long b){13     return a>b?a:b;14 }15 16 long min(long a,long b){17     return a
        
         min(f[then][k-1]*a[end],g[then][k-1]*a[end]))32                     tempmin=min(f[then][k-1]*a[end],g[then][k-1]*a[end]);33             }34             f[end][k]=tempmax;35             g[end][k]=tempmin;36         }37     }38 }39         40 int main(){41     int n,k,d;42     scanf("%d",&n);43     for(int i=1;i<=n;i++)44         scanf("%d",&a[i]);45     scanf("%d%d",&k,&d);46     ability(n,k,d);47     long result=INT_MIN;48     for(int i=k;i<=n;i++){49         if(result
        
       
      
     

 

---恢复内容结束---