TheProduct（Topcoder 10421）

题目描述：

给你一个数列，$k$，$ maxDist$，要你从数列中选出k个数，按照原来的先后顺序排成一个新的数列，要求：新的数列中的每对相邻的数在原数列中的距离不超过$maxDist$。求满足条件的数列中，k个元素乘积的最大值。

输入

保证数列元素个数不超过$50$个。
每个元素在$[-50,50]$的范围内。
$k$在[1,min(10,数列个数)]的范围内。
$maxDist$在$[1,50]$的范围内。

输出

输出最大的乘积

思路：

比较简单的线型动态规划，只要细心些，注意小细节，范围不要搞错剩下的都比较简单。

状态定义

定义$dp[i][j]$为取了i个数字，最后一取的数字的位置为j的最大乘积值。
不过这时要注意，由于元素有可能是负数，所以需要从乘积的最小值转移才能达到最大，所以要再开一个数组mn[][]，来记录最小值，其他定义均与dp数组相同

状态转移

转移唯一需要注意的就是范围(其实也可以不注意范围，每次循环完把该清空的地方清空就行了)。
最初把取第一个数的情况赋上(即$dp(mn)[1][1..n]$),然后每次的状态从$dp[j-1][min(1,i-maxDist)......i-1]$转移得到，至于j的范围，便是$[2,min(k,i)]$.
转移完后最终的答案便是$max(dp[k][k...n],mn[k][k...n])$

总体来说还是比较简单的，一般状态好想到的DP都不难。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <queue>
#include <ctime>
#define FOR(i,l,r) for(int i=(int)l;i<=(int)r;i++)
#define DOR(i,r,l) for(int i=(int)r;i>=(int)l;i--)
#define loop(i,n) for(int i=0;i<(int)n;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define sf scanf
#define pf printf
#define N 55
using namespace std;
typedef long long ll;
int num[N],k,maxDist;
vector<int>numbers;
ll dp[15][N];//取j个,最后一个的位置为k 
ll mn[15][N];
void Max(ll &x,ll y){if(x<y)x=y;}
void Min(ll &x,ll y){if(x>y)x=y;}
class TheProduct {
public:
    long long maxProduct(vector<int>numbers,int k,int maxDist) {
        mms(dp,-63);
        mms(mn,63);
        ll MIN=dp[0][0],MAX=mn[0][0];
        int n=numbers.size();
        //预处理 
        FOR(i,1,n)dp[1][i]=mn[1][i]=numbers[i-1];//取一个数的情况 
        FOR(i,2,n){
            FOR(j,2,min(k,i)){//枚举取数的个数 
                FOR(l,max(1,i-maxDist),i-1){//枚举上一个数的位置 
                    ll lmx=dp[j-1][l];
                    ll lmn=mn[j-1][l];
                    ll num=numbers[i-1];
                    if(lmx!=MIN)Max(dp[j][i],lmx*num),Min(mn[j][i],lmx*num); 
                    if(lmn!=MAX)Max(dp[j][i],lmn*num),Min(mn[j][i],lmn*num);
                    //dp为最大值，mn为最小值 
                }
            }
        }
        ll ans=MIN;
        FOR(i,k,n){
            if(dp[k][i]!=MIN)Max(ans,dp[k][i]);
            if(mn[k][i]!=MAX)Max(ans,mn[k][i]);
            //寻找答案 
        }
        return ans;
    }
};

TheProduct（Topcoder 10421）

原文：https://www.cnblogs.com/Heinz/p/10458876.html