北航算法第三次练习赛-AlvinZH叒掉坑里了 | Eternal_zttz

北航算法第三次练习赛-AlvinZH叒掉坑里了

致敬DP

1. 解题思路

这一题和上一题十分相似,我们可以把问题简化为:将n个金币放入至多m个盒子中,不存在相等数量金币的盒子.

dp[i][j]:将i个金币放入j个盒子的方法数。本题同样可以沿用上一题思想,把答案分成两部分。但是有一个问题是不能有相同数量金币的盒子,如果像上一题一样处理,我们会出现多个1的情况,需要避免这些情况。

  1. 放完之后所有盒子金币数量大于1
  2. 放完之后只有一个盒子金币数量为1

这样分可以保证不会有重复计算,而且不会有相同的情况.状态转移方程为:

1
dp[i][j]=dp[i−j][j]+dp[i−j][j−1]

① dp[i−j][j] : 将(i-j)个金币放到j个盒子,然后这j个盒子每个再放1个金币.表示的是将j个金币分成所有盒子金币数量大于1的方案总数.

② dp[i−j][j−1] : 将(i-j)个金币放到j-1个盒子中去,然后这(j-1)个盒子每个再放1个金币,最后剩下的一个盒子放一个金币.表示的是将j个金币分成至少一个盒子为1的情况.

对比上一题而言,状态转移方程仅仅差了一个字符.

需要注意的是,如果使用dp[50005][50005]是会MLE的,由于本题要求分成不同的数目,1+2+3+…+m=n,于是dp数组变成dp[50005][350]。

优化:
我们可以发现,dp[i][j]只与dp[][j]和dp[][j-1]有关,那么这里可以对空间再次优化,dp数组变为dp[50005][2]

2. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#define MOD 1000007

int n;
int dp[50005][350];

int main(){
while(~scanf("%d", &n)){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int ans = 0;

for (int i = 1; i < 350; ++i) {
for (int j = 0; j <= n; ++j){
if(j - i >= 0)
dp[j][i] = (dp[j-i][i] + dp[j-i][i-1]) % MOD;
}
ans = (ans + dp[n][i]) % MOD;
}
printf("%d\n", ans);
}
}

优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <cstring>
#define MOD 1000007

int n;
int dp[50005][2];

int main(){
while(~scanf("%d", &n)){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
int ans = 0;

for (int i = 1; i < 350; ++i) {
for (int j = 0; j < 350; ++j)
dp[j][i&1] = 0;

for (int j = 0; j <= n; ++j) {
if (j - i >= 0)
dp[j][i&1] = (dp[j - i][i&1] + dp[j - i][(i - 1)&1]) % MOD;
}
ans = (ans + dp[n][i&1]) % MOD;
}

printf("%d\n", ans);
}
}

-------------The End-------------