hdu 2079 - 选课时间

野性酷女 2022-05-28 13:27 147阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=2079][http_acm.hdu.edu.cn_showproblem.php_pid_2079]

# 定位 #

*  排列组合问题
 *  母函数

# 分析 #

*  物品种类数 k，第 i 行输入：物品价值 v\[i\]，物品数量 n2\[i\]。
 *  母函数 
    
    g(x)=(1\+xv\[1\]\+...\+xn2\[1\]v\[1\])...(1\+xv\[i\]\+...\+xn2\[i\]v\[i\])...(1\+xv\[k\]\+...\+xn2\[k\]\]v\[k\])

# 代码 #

**\[cpp\]** view plain copy

print ?

1.  \#include <iostream>  
2.  \#include <stdio.h>  
3.  \#include <string.h>  
4.    
5.  using namespace std;  
6.    
7.  int a\[1001\],b\[1001\];  
8.  int v\[9\],n1\[9\],n2\[9\];  
9.    
10. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
11. Function:       GenerateFunc(int N,int P) 
12. Description:    生成函数系数计算 
13. Input:          int N : 相乘的因子个数 
14.                 int P : 待求的最大指数 
15. Output:         void 
16. Return:         void 
17. Others:         修改的全局变量 a\[\] b\[\] 
18.                 只读的全局变量 v\[\] n1\[\] n2\[\] 
19. \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
20. void GenerateFunc(int N,int P) \{  
21.     memset(a,0,sizeof(a));  
22.     a\[0\]=1;  
23.     for(int i=0; i<N; i++) \{  
24.         memset(b,0,sizeof(b));  
25.         for(int j=n1\[i\]; j<=n2\[i\]&&j\*v\[i\]<=P; j++) \{  
26.             for(int k=0; k+j\*v\[i\]<=P; k++) \{  
27.                 b\[k+j\*v\[i\]\]+=a\[k\];  
28.             \}  
29.         \}  
30.         memcpy(a,b,sizeof(b));  
31.     \}  
32. \}  
33.   
34. int main() \{  
35.     int T;  
36.     memset(n1,0,sizeof(n1));  
37.     scanf(”%d”,&T);  
38.     while(T–) \{  
39.         int n,k;  
40.         scanf(”%d %d”,&n,&k);  
41.         for(int i=0; i<k; i++) \{  
42.             scanf(”%d %d”,&v\[i\],&n2\[i\]);  
43.         \}  
44.         GenerateFunc(k,n);  
45.         printf(”%d\\n”,a\[n\]);  
46.     \}  
47. \}

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">15MS</td> 
   <td align="center">1872K</td> 
   <td align="center">1168B</td> 
   <td align="center">c++</td> 
  </tr> 
 </tbody> 
</table>

[http_acm.hdu.edu.cn_showproblem.php_pid_2079]: http://acm.hdu.edu.cn/showproblem.php?pid=2079