WY6. 合唱团
描述
有 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
Pascal 解法, 执行用时: 1ms, 内存消耗: 256KB, 提交时间: 2018-05-26
program ex;
var n,m,k,d,i,j:integer;
result:double;
f_max:array[-100..100,-1..20] of double;
f_min:array[-100..100,-1..20] of double;
w:array[0..100] of double;
function min_longint(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
function min_double(x,y:double):double;
begin
if x<y then exit(x)
else exit(y);
end;
function max_double(x,y:double):double;
begin
if x>y then exit(x)
else exit(y);
end;
begin
readln(n);
for i:=1 to n do read(w[i]);readln();
readln(m,d);
for i:=-10 to n do
for j:=-10 to m do
begin
f_max[i,j]:=1;
f_max[i,0]:=1;
end;
for i:=1 to n do
for j:=1 to min_longint(m,i) do
for k:=1 to min_longint(d,i) do
begin
f_max[i,j]:=max_double(max_double(f_max[i-k,j-1]*w[i],f_min[i-k,j-1]*w[i]),f_max[i,j]);
f_min[i,j]:=min_double(min_double(f_max[i-k,j-1]*w[i],f_min[i-k,j-1]*w[i]),f_min[i,j]);
end;
result:=-1;
for i:=m to n do
result:=max_double(result,f_max[i,m]);
writeln(result:0:0);
end.
Pascal 解法, 执行用时: 1ms, 内存消耗: 256KB, 提交时间: 2018-05-26
program ex;
var n,m,k,d,i,j:integer;
result:double;
f:array[-100..100,-1..20] of double;
f2:array[-100..100,-1..20] of double;
w:array[0..100] of double;
function min(x,y:double):double;
begin
if x<y then exit(x)
else exit(y);
end;
function min1(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
function max(x,y:double):double;
begin
if x>y then exit(x)
else exit(y);
end;
begin
readln(n);
for i:=1 to n do read(w[i]);readln();
readln(m,d);
for j:=-d to m do f[0,j]:=1;
for i:=1 to n do
for j:=i+1 to m do
f[i,j]:=1;
for i:=1 to n do f[i,0]:=1;
f[0,-1]:=0;f[0,0]:=1;
for i:=1 to n do
for j:=1 to min1(m,i) do
for k:=1 to min1(d,i) do
begin
f[i,j]:=max(max(f[i-k,j-1]*w[i],f2[i-k,j-1]*w[i]),f[i,j]);
f2[i,j]:=min(min(f[i-k,j-1]*w[i],f2[i-k,j-1]*w[i]),f2[i,j]);
end;
result:=-1;
for i:=m to n do
result:=max(result,f[i,m]);
writeln(result:0:0);
end.
C 解法, 执行用时: 1ms, 内存消耗: 356KB, 提交时间: 2018-08-27
#include <stdio.h>
inline long long max(long long a,long long b){return (a>b?a:b);}
inline long long min(long long a,long long b){return (a>b?b:a);}
int main(){
int N,K,D,i,j,k;
long long stu[51],fm[11][51],fn[11][51],ans;
while(~scanf("%d",&N)){
for(i=0;i<N;scanf("%lld",&stu[++i]));
scanf("%d %d",&K,&D);
for(i=0;i<=K;++i)
for(j=0;j<=N;fm[i][j]=fn[i][j]=0,++j);
for(i=1,ans=1LL<<63;i<=N;++i){
fm[1][i]=fn[1][i]=stu[i];
for(k=2;k<=K;++k){
for(j=i-1;j>0 && i-j<=D;--j){
fm[k][i]=max(fm[k][i],max(fm[k-1][j]*stu[i],fn[k-1][j]*stu[i]));
fn[k][i]=min(fn[k][i],min(fn[k-1][j]*stu[i],fm[k-1][j]*stu[i]));
}
}
ans=max(ans,fm[K][i]);
}
printf("%lld\n",ans);
}
return 0;
}
C 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2018-09-09
#include <stdio.h>
inline long long max(long long a,long long b){return (a>b?a:b);}
inline long long min(long long a,long long b){return (a>b?b:a);}
int main(){
int N,K,D,i,j,k;
long long stu[51],fm[11][51],fn[11][51],ans;
while(~scanf("%d",&N)){
for(i=0;i<N;scanf("%lld",&stu[++i]));
scanf("%d %d",&K,&D);
for(i=0;i<=K;++i)
for(j=0;j<=N;fm[i][j]=fn[i][j]=0,++j);
for(i=1,ans=1LL<<63;i<=N;++i){
fm[1][i]=fn[1][i]=stu[i];
for(k=2;k<=K;++k){
for(j=i-1;j>0 && i-j<=D;--j){
fm[k][i]=max(fm[k][i],max(fm[k-1][j]*stu[i],fn[k-1][j]*stu[i]));
fn[k][i]=min(fn[k][i],min(fn[k-1][j]*stu[i],fm[k-1][j]*stu[i]));
}
}
ans=max(ans,fm[K][i]);
}
printf("%lld\n",ans);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 228KB, 提交时间: 2019-01-04
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long long int max(long long int a,long long int b) {return(a>b?a:b);}
long long int min(long long int a,long long int b) {return(a>b?b:a);}
int main(){
int n, k, d, i, j, h;
long long a[51], fmin[10][51], fmax[10][51], MAX=0;
scanf("%d", &n);
for (i=0;i<n;i++)
{
scanf("%lld", &a[i]);
fmin[0][i]=a[i];
fmax[0][i]=a[i];
}
scanf("%d %d", &k, &d);
for(i=1;i<k;i++)
for(j=0;j<n;fmax[i][j]=fmin[i][j]=0,j++);
for (i=1;i<k;i++)
{
for (j=0;j<n;j++)
{
for (h=j+1;h-j<=d&&h<n;h++)
{
fmax[i][h]=max(fmax[i][h],max(fmax[i-1][j]*a[h],fmin[i-1][j]*a[h]));
fmin[i][h]=min(fmin[i][h],min(fmin[i-1][j]*a[h],fmax[i-1][j]*a[h]));
}
}
}
for (i=0;i<n;i++) MAX = max(MAX,fmax[k-1][i]);
printf("%lld", MAX);
return 0;
}