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

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

致敬DP

1. 解题思路

这道题的难度在于如何找到明确状态的过程,题目要求是不允许有空的背包,那么我们可以这样来思考问题:

  1. 存在至少一个背包装的金币数为1
  2. 每个背包装的金币数都大于1

这样分的话可以保证不会有重复的计算出现,那么状态转移方程便是:

1
f[i][j] = (f[i-j][j]+f[i-1][j-1]);

我们来看看代码表示的意思:
f[i−j][j]:将(i-j)个金币放到j个盒子,然后这j个盒子每个再放1个金币。表示的是将i个金币分成所有盒子金币数量大于1的方案总数。例如,求9分解成3份,6(9-3)分成3份可以分为{1,1,4}{1,2,3}{2,2,2},则9可以分为{2,2,5}{2,3,4}{3,3,3},共3种。

f[i−1][j−1] :将(i-1)个金币放到(j-1)个盒子,再来一个盒子放1个。表示的是将i个金币分成至少有一个盒子金币数量为1的方案总数。例如,求9分解成3份,8(9-1)分成2份可以分为{1,7}{2,6}{3,5}{4,4},则9可以分为{1,1,7}{1,2,6}{1,3,5}{1,4,4},共4种。

分类有难度,%AlvinZH.

2. AC代码

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

int n,m;
int f[10010][1010];

int main(){
while(~scanf("%d %d",&n,&m)){
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1;i<=n;i++){
for (int j = 1;j<=m;j++){
if(i - j >=0)
f[i][j] = (f[i-j][j]+f[i-1][j-1])%N;
}
}
printf("%d\n",f[n][m]);
}
}

blog参考:https://www.cnblogs.com/AlvinZH/p/7840604.html

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