如何从数组中找到最小乘积?这是我遇到的问题,尝试的解决方案无效。我做错了什么?
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 theX
-th street to theY
-th street if and only if1 <= Y - X <= K
, whereK
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 theN
-th street). Please, help him to find such a product.Input
The first line of input consists of two integer numbers -
N
andK
- the number of streets and the value ofK
respectively. The second line consist ofN
numbers -A1, A2, ..., AN
respectively, whereAi
equals to the special number of thei
-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 个。
最佳答案
此类问题通常可以通过动态规划来解决:
- 构造一个合适的状态变量:设状态为
S = current street
.让因子在街S
被称为C_S
- 对于每个州
S
,收集可能的 Action :a(S) = {go to any street T for which : 1 <= C_T - C_S <= K, T <=N }, a(N) = {}
. - 引入值(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;
}
输出是8
.
请理解代码,测试它,然后凭良心使用它(无论那意味着什么)。
关于c++ - 寻找最小的产品,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35529260/