链接：https://www.nowcoder.com/test/question/661c49118ca241909add3a11c96408c8?pid=2252286&tid=6652744 来源：牛客网
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？ 输入描述: 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述: 输出一行表示最大的乘积。
输入例子: 3 7 4 7 2 50
输出例子: 49
题目的原型就是求N个数的最大乘积子序列，设dpMax[i][j]位选第A[i]个数时，长度为j的最大的子序列的乘积。最基本的DP式为： dpMax[i][j]=max(dpMax[i][j]，dpMax[k][j-1]*a[i]） 而这个题目的值可能是负的，所以需要用dpMin记录最小子序列的乘积。 再把特殊条件，编号的差不超过 d考虑进去就OK了。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const long long minn=-8e18;long long dpMax[55][11];long long dpMin[55][11];int a[55];int n,k,d;long long Dp(){ memset(dpMax,0,sizeof(dpMax)); memset(dpMin,0,sizeof(dpMin)); for(int i=1;i<=n;i++){ dpMax[i][1]=a[i]; dpMin[i][1]=a[i]; } long long ans=minn; for(int m=2;m<=k;m++){ for(int i=2;i<=n;i++){ for(int j=i-d;j<i;j++){ if(j<0)j=1; dpMax[i][m]=max(max(dpMax[i][m],dpMin[j][m-1]*a[i]),max(dpMax[i][m],dpMax[j][m-1]*a[i])); dpMin[i][m]=min(min(dpMin[i][m],dpMin[j][m-1]*a[i]),min(dpMin[i][m],dpMax[j][m-1]*a[i])); } } } for(int i = 1; i <= n; ++i) { ans = max(ans, dpMax[i][k]); } return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } scanf("%d%d",&k,&d); PRintf("%lld/n",Dp()); return 0;}新闻热点
疑难解答
