上一期版本请见计蒜客 等和的分隔子集

解析

上一期的解法超时了，这期我们来优化一下，仔细观察上期程序，当dp[number][n]中的number很大，但n很小的时候要运行很多次，所以我们来优化这一点，加入附加条件number最大只能是1-n的前n项和。所以我们附加一个number>(1-n)*n/2的情况下，返回0

顺便把dp[number][n]中n很大的情况下进行优化，当number<n时，dp[number][n]=dp[number][number]就可以了

以上思路提交成功Accepted

代码

long dp[1000][50]={0};

long F(int number,int n)

{

if(dp[number][n]!=0)

{

}

else if(number==0)

{

dp[number][n]=1;

}

else if(n==0)

{

return 0;

}

else if(number>(1+n)*n/2)

{

return 0;

}

else if(number>=n)

{

dp[number][n]=F(number,n-1)+F(number-n,n-1);

}

else

{

dp[number][n]=F(number,number);

}

return dp[number][n];

}

int main()

{

int N;

scanf("%d",&N);

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

if(number%2==0)

{

number=number/2;

printf("%lld\n",F(number,N)/2);

}

else

{

printf("0\n");

}

return 0;

}