首页 > 代码库 > （dp）openjudge 复杂的整数划分问题

（dp）openjudge 复杂的整数划分问题

2024-10-31 09:38:39   210人阅读

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。

输入标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 
(0 < N <= 50, 0 < K <= N)输出对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目样例输入

5 2

样例输出

2
3
3

提示第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1

虽然是3个问题，但其实都是通过讨论1的是否存在推出的转移方程。并且可以证明第二种和第三种的个数永远是相等的。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 #include <set>
 9 #include <map>
10 #include <list>
11 #include <vector>
12 #include <stack>
13 #define mp make_pair
14 //#define P make_pair
15 #define MIN(a,b) (a>b?b:a)
16 //#define MAX(a,b) (a>b?a:b)
17 typedef long long ll;
18 typedef unsigned long long ull;
19 const int MAX=1e2+5;
20 const int INF=1e8+5;
21 using namespace std;
22 //const int MOD=1e9+7;
23 typedef pair<ll,int> pii;
24 const double eps=0.00000001;
25 
26 int n;
27 int dp[MAX][MAX],dp2[MAX][MAX],dp3[MAX][MAX];
28 int get_dp(int x,int y)
29 {
30     if(y>x)
31         return dp[x][y]=0;
32     if(dp[x][y]>=0)
33         return dp[x][y];
34     if(y<=1)
35         return dp[x][y]=y;
36     return dp[x][y]=get_dp(x-y,y)+get_dp(x-1,y-1);
37 }
38 int get_dp2(int x,int y)
39 {
40     if(dp2[x][y]>=0)
41         return dp2[x][y];
42     if(y*(y+1)/2>x)
43         return dp2[x][y]=0;
44     if(y<=1)
45         return dp2[x][y]=y;
46     return dp2[x][y]=get_dp2(x-y,y-1)+get_dp2(x-y,y);
47 }
48 int get_dp3(int x,int y)
49 {
50     if(dp3[x][y]>=0)
51         return dp3[x][y];
52     if(y>x)
53         return dp3[x][y]=0;
54     if(y==0)
55         return dp3[x][y]=0;
56     if (y==1)
57         return dp3[x][y]=x%2;
58     return dp3[x][y]=get_dp3(x-1,y-1)+get_dp3(x-2*y,y);
59 }
60 int z;
61 int main()
62 {
63     memset(dp,-1,sizeof(dp));
64     memset(dp2,-1,sizeof(dp2));
65     memset(dp3,-1,sizeof(dp3));
66     while(~scanf("%d%d",&n,&z))
67     {
68         printf("%d\n",get_dp(n,z));
69         int an=0;
70         for(int s=1;s<=n;s++)
71         {
72             int tem=get_dp2(n,s);
73             an+=tem;
74         }
75         int an2=0;
76         printf("%d\n",an);
77         for(int s=1;s<=n;s++)
78         {
79             int tem=get_dp3(n,s);
80             an2+=tem;
81         }
82         printf("%d\n",an,an2);
83     }
84 }

 

（dp）openjudge 复杂的整数划分问题


联系
我们