网址：http://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8
……想了半天，居然想不出来如何解释状态转移方程是怎么想出来的。这只能说，是套路。
这个思考过程待填，下面直接说状态的定义。
f [ i ] [ j ] [ 最大 / 最小 ]
分别表示，以第i个人为最后一个（也是必选的）人，加上这个人，已经选了 j 个人，最大可能的乘积和最小可能的乘积。
——为什么不是只记录最大的，还要记录最小的？
——因为最小的，很可能是一个负数，有着极大的绝对值，再乘一个负数，就变成最大的正数，也就是最优解了。
然后考虑，这个状态由哪些状态转移过来？
j 人，明显是从j-1个人的状态，最后加1个人（当前考虑的 i ）而来。
第 i 人，根据题目要求，编号差不能大于d。那我们就往前观察最多d个人，从i-d到i-1，选了j-1个人中，选择和自己相乘，最大/最小的。
注意考虑边界条件：只选了一个人，就是 i 自己。
最后，解很大，请使用long long（C++）/ long (Java、C#)来保存中间计算结果。
[cpp] view plain copy #include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <math.h> #include <algorithm> using namespace std; typedef long long ll; int a[55]; ll f[55][15][2]; int main(){ int n,kk,d; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } scanf("%d%d",&kk,&d); ll ans=0; for(int i=1;i<=n;i++){ f[i][1][0]=f[i][1][1]=a[i]; for(int j=2;j<=kk;++j){ for(int k=i-1;k>=max(i-d,1);--k){ f[i][j][0]=max(f[i][j][0],max(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i])); f[i][j][1]=min(f[i][j][1],min(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i])); } } ans=max(ans,max(f[i][kk][0],f[i][kk][1])); } printf("%lld\n",ans); return 0; }
