3675 - 切绳子
一段长为n的绳子，可以切成很多段，并且有好几种切法，比如当n=4时，可以切成1 1 1 1， 1 1 2，1 3，2 2。
也就是n=4时，有4种切法。现在给定n，要求输出有几种切法。
Input
每组测试数据包含一个整数n
Output
每行一个测试数据，1<=n<=60
Examples
Input
4 1
Output
4 0
Solution C
#include<stdio.h> int n; void qie(int l,int i) { int j; for(j=i;j<=l;j++) { l-=j;if(l==0)n++; if(l>=j)qie(l,j); l+=j; } } int main() { int l; while(scanf("%d",&l)==1) { n=0; qie(l,1); printf("%d\n",n-1); } return 0; }
Solution C++
#include <stdio.h> int dp[80][80]; int main() { int i,j; int n; dp[0][0]=0; for(j=0;j<80;j++) dp[0][j]=1; for(i=0;i<80;i++) dp[i][0]=0; for(j=1;j<80;j++) dp[1][j]=1; for(i=2;i<80;i++) for(j=1;j<80;j++) { if(j>i) dp[i][j]=dp[i][i]; else dp[i][j]=dp[i][j-1]+dp[i-j][j]; } while(scanf("%d",&n)!=EOF) { printf("%d\n",dp[n][n]-1); } return 0; }