n的m划分

n的m划分：

dp[i][j]表示j的i划分，也就是将j颗球放入i个袋子里面，最后的答案是dp[m][n]

状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-i];

划分方法有两种：①有的袋子不放球：dp[i-1][j]，比如n=4,m=3,那么可以有2+2或者1+3或者4的方法分完四颗球，i-1表示至少有一个袋子不放球，j表示一共有j颗球

②所有的袋子都不为空，至少有一颗球：dp[i][j-i]，也就是1+1+2的方法，i表示每个袋子都放球，

j-i表示每个袋子都放上一颗球之后剩下j-i颗球

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include<string>
 9 #include
10 #include
11 using namespace std;
12 int n,m,M;
13 int dp[1010][1010];
14 void solve()
15 {
16     dp[0][0]=1;
17     for(int i=0;i<=m;i++)
18     {
19         for(int j=0;j<=n;j++)
20         {
21             if(j-i>=0)
22             {
23                 dp[i][j]=(dp[i][j-i]+dp[i-1][j])%M;
24             }
25             else
26             {
27                 dp[i][j]=dp[i-1][j];
28             }
29         }
30     }
31     printf("%d\n",dp[m][n]);
32 }
33 int main()
34 {
35     scanf("%d%d%d",&n,&m,&M);
36     solve();
37     return 0;
38 }
oj

相关

uoj316【NOI2017】泳池

Gojs

【Baltic2003】【BZOJ1370】Gang团伙（并查集，拆点）

poj 2301（水题）

.NET Core项目从xproj+project.json向csproj迁移简介

poj2917

P2859 [USACO06FEB]Stall Reservations S POJ3190

【YBTOJ高效进阶 21190】欧拉函数（数学）

POJ1002_487-3279_C++

【数据结构】【图文】【oj习题】 图的拓扑排序（邻接表）

【数据结构oj】树的度

[BZOJ]1026[SCOI2009]windy数

标签