hdu--1028--dp||递推||母函数

这题开始的时候犯了和做--调皮的小明的时候一样的错误去dfs了果断TLE啊

然后想起来就dp去做...

还有一些别的做法有人用递推或者母函数做的其实递推的话还是和dp有点像的

还有一种记忆化搜索的方法太流弊了

我把它都贴出来好了

 1 /*
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int n , cnt;
 7 void dfs( int pos , int sum )
 8 {
 9     if( sum==n )
10     {
11         cnt++;
12         return;
13     }
14     for( int i = pos ; i<=n ; i++ )
15     {
16         if( sum+i <= n )
17         {
18             dfs( i , sum+i );
19         }
20     }
21 }
22 
23 int main()
24 {
25     while( cin>>n )
26     {
27         cnt = 0;
28         dfs(1,0);
29         cout << cnt << endl;
30     }
31     return 0;
32 }
33 */
34 
35 #include <iostream>
36 #include <cstring>
37 using namespace std;
38 
39 const int size = 125;
40 int dp[size][size];
41 void init( )
42 {
43     memset( dp , 0 , sizeof(dp) );
44     for( int i = 0 ; i<size ; i++ )
45     {
46         dp[i][0] = 1;
47     }
48     for( int i = 1 ; i<=120 ; i++ )
49     {
50         for( int j = 1 ; j<=120 ; j++ )
51         {
52             if( j>=i )
53             {
54                 dp[i][j] = dp[i-1][j] + dp[i][j-i];
55             }
56             else
57             {
58                 dp[i][j] = dp[i-1][j];
59             }
60         }
61     }
62 }
63 
64 int main()
65 {
66     int n;
67     init();
68     while( cin>>n )
69     {
70         cout << dp[n][n] << endl;
71     }
72     return 0;
73 }

View Code

注释的是 dfs =-= a sorrow story

下面是递推的----http://fudq.blog.163.com/blog/static/191350238201162535640887/ 来自这里

首先，我们引进一个小小概念来方便描述吧，record[n][m]是把自然数划分成所有元素不大于m的分法，例如：

当n=4，m=1时，要求所有的元素都比m小，所以划分法只有1种：{1，1，1，1}；

当n=4，m=2时，。。。。。。。。。。。。。。。。只有3种{1，1，1，1},{2，1，1}，{2，2}；

当n=4，m=3时，。。。。。。。。。。。。。。。。只有4种{1，1，1，1},{2，1，1}，{2，2},{3,1}；

当n=4，m=5时，。。。。。。。。。。。。。。。。只有5种{1，1，1，1},{2，1，1}，{2，2},{3,1},{4}；

从上面我们可以发现：当n==1||m==1时，只有一种分法；

当n<m时，由于分法不可能出现负数，所以record[n][m]=record[n][n];

当n==m时，那么就得分析是否要分出m这一个数，如果要分那就只有一种{m}，要是不分，那就是把n分成不大于m-1的若干份；即record[n][n]=1+record[n][n-1];

当 n>m时，那么就得分析是否要分出m这一个数，如果要分那就{{m},{x1,x2,x3..}}时n-m的分法record[n-m][m]，要是不分，那就是把n分成不大于m-1的若干份；即record[n][n]=record[n-m][m]+record[n][m-1];

那么其递归式：

record[n][m]= 1 (n==1||m==1)

record[n][n] (n<m)

1+record[n][m-1] (n==m)

record[n-m][m]+record[n][m-1] (N>m)

这是它的核心思想

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int i,j,n,a[125][125]={0};
 7     for(i=1;i<125;i++)
 8         a[i][1]=a[1][i]=1;
 9     for(i=2;i<125;i++)
10     {
11         for(j=2;j<125;j++)
12         {
13             if(i<j)
14                 a[i][j]=a[i][i];
15             if(i==j)
16                 a[i][j]=a[i][j-1]+1;
17             if(i>j)
18                 a[i][j]=a[i-j][j]+a[i][j-1];
19         }
20     }
21     while(scanf("%d",&n)!=EOF)
22     {
23         printf("%d
",a[n][n]);
24     }
25     return 0;
26 }

View Code

至于那母函数的代码就很普通不贴了就是个模板母函数题

记忆化搜索的看下

可以这样考虑将，n构造为非递增子序列的和一共有多少个这样的序列。假设一个状态，起一个元素的为last，现在需要分配的剩余数为n。所以一开始状态应该为fun(n,last)。下一步只需要继续构造非递增子序列一直到n为1。用记忆搜索实现：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAX = 121 ;
 4 int count = 0 ;
 5 int vis[MAX][MAX] ;
 6 int fun(int n ,int last)
 7 {
 8     
 9     if(n <= 1)
10     {
11         return 1;
12     }
13     
14     if(vis[n][last] > 0)
15     {
16         return vis[n][last] ;
17     }
18     
19     int sum = 0 ;
20     for(int i = n ; i >= 1 ; i--)
21     {
22         if(i <= last)
23         {
24             vis[n-i][i] = fun(n-i ,i) ;
25             sum += vis[n-i][i] ;
26         }
27     }
28     return sum ;
29 }
30 
31 int main()
32 {
33     int n;
34     while(~scanf("%d" , &n))
35     {
36         count=0;
37         memset(vis , 0 , sizeof(vis)) ;
38         printf("%d
" , fun(n,n)) ;
39     }
40     return 0 ;
41 }

View Code

today:

　　当你孤独的时候是你最不孤独的时候

just follow your heart