首页 > 代码库 > hdu--1028--dp||递推||母函数
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 else57 {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 }
注释的是 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\n",a[n][n]);24 }25 return 0;26 }
至于那 母函数的代码 就很普通 不贴了 就是个模板母函数题
记忆化搜索的看下
可以这样考虑将，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\n" , fun(n,n)) ;39 }40 return 0 ;41 }
today:
当你孤独的时候 是你最不孤独的时候