c++ - 在不使用图形的情况下以最小产品从第一个索引到最后一个索引？

Question

解决这个 problem在 codechef 上:

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

可以使用基于此tutorial 的图 来解决我试图在不使用图表的情况下仅使用递归 和DP 来解决它。我的做法:

1. 获取一个数组并计算到达每个索引的最小乘积并将其存储在相应的索引中。
2. 这可以使用自上而下的方法计算并递归发送索引(符合条件)直到达到起始索引。
3. 在所有计算值中存储最小值。
4. 如果已经计算出来，返回它，否则计算。

代码:

 #include<iostream>
 #include<cstdio>
 #define LI long int
 #define MAX 100009
 #define MOD 1000000007
 using namespace std;
 LI dp[MAX]={0};
 LI ar[MAX],k,orig;
 void cal(LI n)
 {
       if(n==0)
          return;
       if(dp[n]!=0)
          return;
       LI minn=MAX;
       for(LI i=n-1;i>=0;i--)
       {
          if(ar[n]-ar[i]<=k && ar[n]-ar[i]>=1)
          {
              cal(i);
              minn=(min(dp[i]*ar[n],minn))%MOD;
          }
       }
       dp[n]=minn%MOD;
       return;
 }

 int main()
 {
    LI n,i;
    scanf("%ld %ld",&n,&k);
    orig=n;
    for(i=0;i<n;i++)
       scanf("%ld",&ar[i]);
    dp[0]=ar[0];
    cal(n-1);
    if(dp[n-1]==MAX)
       printf("0");
    else printf("%ld",dp[n-1]);
    return 0;
}

已经 2 天了，我已经检查了每个角落的案例和约束，但它仍然给出了错误的答案!解决方案有什么问题？

需要帮助。

Answer 1

分析

有很多问题。这是我发现的:

1. 您无故将产品限制为低于 100009 的值。产品可以比那个高得多(这确实是问题只询问值模 1000000007 的原因)
2. 您限制从special number 差异为K 的街道移动，而问题陈述表明您可以在index 的任何城市之间移动> 差异不如 K
3. 在您的动态规划函数中，您计算​​乘积并存储乘积的模数。这可能会导致问题，因为大数的模可能低于小数的模。这可能会破坏以后的计算。
4. 您使用的整数类型 long int 太短。
5. 您的算法的复杂度太高。

从所有这些问题中，最后一个是最严重的。我通过更改整个方法并使用更好的数据结构来修复它。

第一个问题

在您的 main() 函数中:

if(dp[n-1]==MAX)
   printf("0");

在您的cal() 函数中:

LI minn=MAX;

您应该将此行替换为:

LI minn = std::numeric_limits<LI>::max();

不要忘记:

#include <limits>

第二个问题

   for(LI i=n-1;i>=0;i--)
   {
      if(ar[n]-ar[i]<=k && ar[n]-ar[i]>=1)
      {
          . . .
      }
   }

您应该替换 for 循环条件:

  for(LI i=n-1;i>=n-k;i--)

并完全删除特殊号码的条件。

第三个问题

你正在寻找特殊数乘积最小的路径。在您当前的设置中，您在取乘积的模后比较路径的乘积。这是错误的，因为较高数字的模数可能会变得非常低(例如，乘积为 1000000008 的路径的模数将为 1，您将选择此路径，即使存在其乘积仅为 2 的路径)。

这意味着您应该比较真实的产品，而不是取模。由于这些产品可能会变得非常高，您应该取它们的对数。这将允许您使用简单的 double 比较产品。请记住:

log(a*b) = log(a) + log(b)

第四题

使用unsigned long long。

第五题

我修复了所有这些问题并在 codechef CHRL4 上提交。除了一个测试用例，我接受了所有测试用例。未接受的测试用例是因为超时。这是因为您的算法的复杂度为 O(k*n)。

您可以使用自下而上的动态规划方法实现 O(n) 复杂度，而不是自上而下，并使用将返回 k 的最小对数值的数据结构 以前的街道。您可以查找滑动窗口最小算法来了解如何做。

引用资料

• numeric_limits::max()
• 我自己的 codechef CHRL4 解决方案:bottom-up dp + sliding window minimum