合唱团---2017校招（动态规划）

合唱团

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

3
7 4 7
2 50

输出

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

问题分解：分解是关键，设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<stdio.h>
 2 #include<math.h>
 3 #include<limits.h>
 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<b?a:b;
18 }
19 void ability(int n,int kk,int d){
20     for(int i=1;i<=n;i++){
21         f[i][1]=a[i];
22         g[i][1]=a[i];  
23     }
24     for(long k=2;k<=kk;k++){
25         for(int end=k;end<=n;end++){
26             long tempmax=INT_MIN;
27             long tempmin=INT_MAX;
28             for(int then=max1(k-1,end-d);then<=end-1;then++){
29                 if(tempmax<max(f[then][k-1]*a[end],g[then][k-1]*a[end]))
30                     tempmax=max(f[then][k-1]*a[end],g[then][k-1]*a[end]);
31                 if(tempmin>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<f[i][k])result=f[i][k];
50     }
51     printf("%ld",result);
52 
53     return 0;
54 }

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