poj1664 放苹果 <整数拆分>

View Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 int dp[12][12];
 8 void fuck(  )
 9 {
10     dp[1][1]=1;     
11     for( int i=2; i<12; ++ i ){
12         dp[i][1]=dp[1][i]=1;    //一个盘子或者一个苹果时 
13         for(int j=2; j<12; ++ j ){
14             if( i>j )           // 苹果数大于盘子数时分两种情况讨论，一种是至少有一个盘子里不放苹果，这样子就相当于dp[i][j-1],
15                                 //第二种是，先取出j个苹果一个盘子里放一个，再将剩下的i-j个苹果放到n个盘子里去，即dp[i-j][j];       
16                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
17             else if(i==j) dp[i][j]=dp[i][j-1]+1;// 苹果数等于盘子数时分两种情况讨论，一种是一个盘子里放一个，只是一种，
18                                                 //第二种是，至少有一个盘子里不放苹果这就相当于是dp[i][j-1]; 
19                 else dp[i][j]=dp[i][i];   // 苹果数小于盘子数时  最多放苹果数的盘子 
20         }
21     }
22 }
23 int main( )
24 {
25     int T, N, M;
26     fuck( );
27     scanf( "%d", &T );
28     while( T -- ){
29         scanf( "%d%d", &N, &M);
30         printf( "%d\n", dp[N][M] );
31     } 
32     return 0;
33 }

链接：http://acm.nankai.edu.cn/p1046.html

整数拆分的本质就是放苹果，不过有点要求就是N个苹果必须放在N个盘子里。

View Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 int dp[100][100];
 9 
10 int fuck1(int n,int m)// 递归版本 
11 {
12     if((n<1)||(m<1)) return 0;
13     if(n==1||m==1) return 1;
14     if(n<m) return fuck1(n,n);
15     if(n==m) return fuck1(n,m-1)+1;
16     return fuck1(n,m-1)+fuck1(n-m,m);
17 }
18 
19 void fuck(  )//非递归 
20 {     
21     for( int i=1; i<=80; ++ i ){
22         dp[i][1]=dp[1][i]=1;    
23         for(int j=2; j<=80; ++ j ){
24             if( i>j ) {
25                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
26             }          
27                 
28             else if( i==j ) {
29                 dp[i][j]=dp[i][j-1]+1;
30             } 
31             else if( i<j ){
32                 dp[i][j]=dp[i][i];
33             }
34         }
35     
36     }
37 }
38 int main( )
39 {
40     int T, N, M;
41     fuck( );
42     while(  scanf( "%d", &T )==1 ){
43 
44         printf( "%d\n", dp[T][T] );
45     
46     } 
47     return 0;
48 }