題意做法:DP
思路:
設(shè)f[i][j]表示前i個(gè)數(shù)能得到j的集合數(shù)(當(dāng)然這里每一個(gè)結(jié)果都多算了一次,因?yàn)閮蓚€(gè)想等的結(jié)果的兩個(gè)集合都算了,比如說(shuō)前3個(gè)數(shù),有{1,2}和{3}但是如果輸入3的話,結(jié)果只能輸出1.不過(guò)這沒(méi)事,因?yàn)?span style="COLOR: blue">每個(gè)都多算了一次
,最后的結(jié)果只要除
2就行了
),f[i][j](0<=j<=(i+1)*i/2)可以由
f[i-1][k]得到
轉(zhuǎn)移方程:
for i = 2 to n
f[i][i] =1;/*這選自己*/
j = i – 1;
for k = 0 to (j+1)*j/2 /*f[i][k] <----f[i-1][k] f[i][i+k] <-----f[i-1][k]*/
if(f[j][k] > 0)
f[i][k] += f[j][k];
f[i][k+i] += f[j][k];
最后還有一點(diǎn)就是N = 39時(shí)結(jié)果很大要用long long或者__int64存