c++ - 寻找最小的产品

Question

如何从数组中找到最小乘积？这是我遇到的问题，尝试的解决方案无效。我做错了什么？

https://www.codechef.com/problems/CHRL4

After visiting a childhood friend, Chef wants to get back to his home. Friend lives at the first street, and Chef himself lives at the N-th (and the last) street. Their city is a bit special: you can move from the X-th street to the Y-th street if and only if 1 <= Y - X <= K, where K is the integer value that is given to you. Chef wants to get to home in such a way that the product of all the visited streets' special numbers is minimal (including the first and the N-th street). Please, help him to find such a product.

Input

The first line of input consists of two integer numbers - N and K - the number of streets and the value of K respectively. The second line consist of N numbers - A1, A2, ..., AN respectively, where Ai equals to the special number of the i-th street.

Output

Please output the value of the minimal possible product, modulo 1000000007. Constraints

1 ≤ N ≤ 10^5 1 ≤ Ai ≤ 10^5 1 ≤ K ≤ N

Example

Input:

4 2 1 2 3 4.

Output: 8

#include <iostream>
using namespace std;

int P(int A[], int N, int K) {
    if (N == 1) return A[0];

    int m = A[0], prod = m;
    for (int i = 1; i < N; ++i) {
        if (1 <= A[i]-m && A[i]-m <= K) {
            prod *= A[i];
        }
    }
    return prod;
}

int main() {
    int A[] = {1, 2, 3, 4};
    cout << P(A, 4, 2);
}

我得到 6 个而不是 8 个。

Answer 1

此类问题通常可以通过动态规划来解决:

1. 构造一个合适的状态变量:设状态为S = current street .让因子在街S被称为C_S
2. 对于每个州 S ，收集可能的 Action :a(S) = {go to any street T for which : 1 <= C_T - C_S <= K, T <=N }, a(N) = {} .
3. 引入值(value)函数V(S) = minimal product to get from S to N .设置V(N) = C_N .

有了所有这些，现在可以从 N 向后求解贝尔曼方程，特别是值 V(0)寻求:

V(S) = min_{allowed T} { V(T)*C_S }

示例实现:

int main()
{
    int N = 4;
    int K = 2;

    std::vector<int> C{1,2,3,4};
    std::vector<int> V(N);
    V.back() = C.back();

    for(int i = N - 2; i>= 0; --i)
    {
        int min = std::numeric_limits<int>::max(); //possible overflow here,
                                                   //better change that
        for(int j=i+1; j< N; ++j)
        {
            double DeltaC = C[j] - C[i];
            if(DeltaC <= K && DeltaC >= 1)
            {
                double vt = V[j] * C[i];
                if(vt < min)
                {
                    min = vt;
                }
            }
        }
        V[i] = min;
    }

    std::cout<<V[0]<<std::endl;
}

DEMO

输出是8 .

请理解代码，测试它，然后凭良心使用它(无论那意味着什么)。