热度指数：93875时间限制：1秒空间限制：32768K 算法知识视频讲解 有 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 输出 49
#define MAIN #ifdef MAIN #include <stdio.h> #include <limits.h> #include <algorithm> #include <string.h> void shuchu(long long int a[][15], int il, int jl) { for(int i = 1; i < il; i++){ for(int j = 1; j < jl; j++) { printf("I64d", a[i][j]); } printf("\n"); } } int main() { int n; scanf("%d", &n); int a[n+1]; for(int i = 1; i <=n; i++) { scanf("%d", &a[i]); } int k, d; scanf("%d %d", &k, &d); //int f[n+1][k+1]; //int g[n+1][k+1]; long long int f[n+1][15]; long long int g[n+1][15]; //printf("%d\n", sizeof(f)); memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); for(int i = 1; i <= n; i++) { f[i][1] = a[i]; g[i][1] = a[i]; } for(int ck = 2; ck <= k; ck++) { //第一个循环是为了固定最后一个，从前面选k-1个 for(int cn = ck; cn <= n; cn++) { //<=n是为了更新完第ck列， long long int tmax = LONG_LONG_MIN; long long int tmin = LONG_LONG_MAX; for(int left = std::max(ck-1,cn-d);left<=cn-1; left++) { long long int tempmax = std::max(f[left][ck-1]*a[cn],g[left][ck-1]*a[cn]); long long int tempmin = std::min(f[left][ck-1]*a[cn],g[left][ck-1]*a[cn]); if(tmax < tempmax) { tmax = tempmax; } if(tmin > tempmin) { tmin = tempmin; } } f[cn][ck] = tmax; g[cn][ck] = tmin; } } long long int max_value = LONG_LONG_MIN; for(int cn = k; cn <= n; cn++) { if(f[cn][k]>max_value) max_value = f[cn][k]; } printf("%lld\n",max_value); return 0; } #endif