当N> = 10时，这段代码为什么会冻结？

Question

这是一个用C++ 11编写的程序。

当text.in的值为N < 10此程序正常工作。然而，当N增加到11时，它会冻结，似乎永远持续下去。为什么会这样呢？

#include <cstdio> 
using namespace std; 

int dp[40][391]={0}; 

int main() { 
    FILE* in = fopen("text.in","r"); 
    FILE* out = fopen("text.out","w"); 
    int N; 
    fscanf(in,"%d",&N); 
    int sum = N*(N+1)/2; 
    for (int i=0; i<=N; i++) dp[0][i]=1; 
    if (sum%2==1) {fprintf(out,"0"); return 0;} 
    for (int n=1; n<=sum; n++) { 
     for (int k=1; k<=N; k++) { 
      if (n-k>=0) dp[n][k]=dp[n-k][k-1]; 
      dp[n][k]+=dp[n][k-1]; 
     } 
    } 
    fprintf(out,"%d",dp[sum/2][N]/2); 
    return 0; 
} 

Answer 1

我很惊讶与N == 9一起使用。

您定义

int dp[40][391] 

和你读/写在它

if (n-k>=0) dp[n][k]=dp[n-k][k-1]; 
    dp[n][k]+=dp[n][k-1]; 

带有第一索引n与范围从1到sum其中

int sum = N*(N+1)/2; 

所以如果N < 9， sum是低于40;如果N>=9，sum大于40 [sum == 45对于N == 9; sum == 55 for N == 10; sum = 66对于N == 11。

因此，如果您使用N == 11编写dp[66][k]，那么当第一个索引的最高合法值为39时。

精彩的灾难食谱。