当前位置:首页 > 高性能开发 > 数据结构与算法

POJ1664(简略动态规划)

优良自学吧提供POJ1664(简略动态规划),POJ1664(简单动态规划) 1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5 int f[

POJ1664(简单动态规划)
 1 #include<iostream>
 2 #include<string> 
 3 #include<cstring>
 4 using namespace std;
 5 int f[12][12];
 6 void F(int m,int n)
 7 {
 8     int i,j;
 9     for(int i=0;i<=m;i++)
10     {
11         f[i][1]=1;
12         f[i][0]=1;
13     }
14     
15     for(int j=0;j<=n;j++)
16     {
17         f[1][j]=1;
18         f[0][j]=1;
19     }    
20     
21      for(i=2;i<=m;i++)                      
22         for(j=2;j<=n;j++)
23         {  
24             if(i>=j)                              //当苹果数大于盘子的时候 ①假设有一个空盘 ②另外为n个盘子都不为空,则先将n个苹果一个一个放入n的盘子中,剩下的m-n个苹果再放入n个盘子中。此放法就相当于m-n个苹果放n个盘子里面,有f[m-n][n]种放法。
25                 f[i][j]=f[i][j-1]+f[i-j][j];  
26             if(i<j)                              //当盘子数大于苹果数的时候   相当于那些多余的盘子里面没有东西(抽屉原理?) 
27                 f[i][j]=f[i][i];  
28     
29         }
30 }
31     
32 int main()
33 {
34     int t,M,N,K;
35     cin>>t;
36     while(t>0)
37     {
38         t--;
39         cin>>M>>N;
40         memset(f,0,sizeof(f));  
41         F(M,N) ;
42         cout<<f[M][N]<<endl;
43         
44     }
45     
46     return 0;
47 }
Memory                                                            Time  
216K                                                             0MS

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢