上一期版本请见计蒜客 等和的分隔子集
解析
上一期的解法超时了，这期我们来优化一下，仔细观察上期程序，当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;
}
