题面：

题解：

dp

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

模型转化为求选若干个数，填满sum/2的空间的方案数，就是背包啦

显然如果sum%2!=0是没有答案的，就特判掉

F[i][j]表示对于前i个数，和为j的方案数

F[0][0]=1;

F[i][j]+=F[i-1][j-i] (j>=i)

转化为

for(int i=1;i<=N;i++)

for(int j=sum/2;j>=i;j--)

F[j]+=F[j-i];

答案是F[sum/2]/2，因为真实题目要求是划分嘛，然后你写成选出了你又把它放A又放B当然得/2了。。

反正就是这样

代码：

1 #include
      
        2 #define ll long long 3 using namespace std; 4 const int maxn=45,maxsum=maxn*(1+maxn)/2; 5 int N,sum,hf; 6 ll F[maxsum/2]; 7 int main(){ 8     scanf("%d",&N); 9     sum=N*(N+1)/2;10     if(sum%2){11         printf("0\n");12         return 0;13     }14     hf=sum/2;15     F[0]=1;16     for(int i=1;i<=N;i++)17         for(int j=hf;j>=i;j--)18             F[j]+=F[j-i];19     printf("%lld\n",F[hf]/2);20     return 0;21 }
      

 

---

By:AlenaNuna