|
dp题光看代码可能比较抽象（本菜鸡是这样的），所以我讲的略小白一点，大佬就别看了orz
题目描述 给你一个n块积木，每个积木块都是立方体，现在把它们排列一排，成m列，要求每列上至少有1个积木，且从左到右，每列的积木数量呈严格单调下降。比如8块积木，排成3列，那么合法的安排方案为521或者431。请问n块积木按规则排成m有多少种不同的方案？ 输入 第一行是一个整数T(1≤T≤1000)，表示样例的个数。 以后每个样例占一行，为两个整数?n(1≤n≤100),m(1≤m≤10)。 输出 依次每行输出一个样例的结果，为一个整数。 样例输入 2
8 3
13 4
样例输出 2
3
样例解释 第二个样例的合法方案为7321,6421,5431 | | |
先不多说，我喜欢先放代码。代码略丑（见谅）
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
int i, j, k, l, n, m,sum;
scanf("%d", &t);
while (t--) {
int a[101][11][110];//a[i][j][k]为i块积木，共j列，第一列为k个方块的方案数
memset(a, 0, sizeof(a));
a[1][1][1] = 1;
scanf("%d %d", &n, &m);
for (i = 2; i <= n; i++) {
for (j = 1; j <= m; j++) {
for (k = 1; k <= i; k++) {
if (i == k && j == 1) { //如果排成一列，第一列为总积木时，只有一种情况
a[i][j][k] = 1;
} else {
for (l = k - 1; l >= 1; l--) {
a[i][j][k] += a[i - k][j - 1][l];
}
}
}
}//排几列
}
sum = 0;
for (i = 1; i <= n; i++) {
sum += a[n][m][i];
}
printf("%d\n", sum);
}
return 0;
}
举个栗子(手动dp）：
有6个积木，要排3列，sum=a[6][3][1]+a[6][3][2]+a[6][3][3]+...a[6][3][6]
而a[6][3][2]=a[4][2][1]，a[4][2][1]=a[3][1][0]=0
a[6][3][3]=a[3][2][1]+a[3][2][2]，a[3][2][2]=a[1][1][1]=1
a[6][3][4]=a[2][2][1]+a[2][2][2]+a[2][2][3]，a[2][2][1]=a[1][1][0]=0
...后面的更不可能了
这个搭建过程：先搭第一列，第一列数字确定下来之后，sum=第二列的情况（记得把总积木和列数都要减去相应的），即第二列分别为1，2，3...n-第一列的积木。
而第二列的每一种的情况又分别=第三列的情况...
这样一直继续下去，就是一个dp过程。
可以总结出方程a[i][j][k]=a[i-k][j-1][1]..........+a[i-k][j-1][k-1]
这里的k是可以优化的，上面的栗子中可以看见，有一些k完全是不可能存在的，都已经超过总积木，或者有些列已经为0了，具体优化留给你们想叭。
代码思想：
确定下核心方程之后，就是依次枚举i，j，k，因为dp的终点我们应该是确定的，就是排成一列，第一列就是总积木时，这时的情况是1。而其他情况都可以用方程运算。
这边可以把整个搭建过程放到while函数的外面，再输入输出，这样代码会更好看啦（但是我懒）。
如果还是有点晕的欢迎留言讨论，然后要是说错了欢迎大佬捉虫QwQ
|