好久没有写博客了，回学校了也没啥时间可以摸鱼了（主要还是懒🤣）
晚上参加了东哥家的笔试，30道选择+两道编程。整体难度还好，（Ball Ball 东哥给孩子一个机会吧！看在老PLUS会员的份上）
但是第二道编程题想要记录一下，最后一分钟才调出来，刺激！🤪
题目
从CSDN上扒了张题图。
思路：
第一眼看过去，这就是一道典型的完全背包求方案数的问题呀！刷刷把完全背包写了一遍。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
using namespace std;
typedef long long LL;
const int N = 110, M = 1010, mod = 1e9 + 7;
int vals[N];
LL f[N][M];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> vals[i];
for(int i = 0; i <= n; ++i)
f[i][0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int k = 0; k <= j / vals[i]; ++k)
f[i][j] = (f[i][j] + f[i - 1][j - k * vals[i]]) % mod;
cout << f[n][m] << endl;
return 0;
}
|
信心满满自测样例……（淦，咋对不上？尴尬）没事，可能是我完全背包太久没写哪里出了点差错，调就完事儿了。
30 Minutes Later~~
淦，这完全背包没毛病呀？到底啥情况？样例倒是为什么会是5，我手工模拟也是3（黑人问号？？？）
终于想起来再读一遍题目。
“使用的牌的种类或数量不同代表不同的方案，改变牌的顺序同样代表不同的方案”
真想扇死自己，题都没读完直接开敲，hh。
AC代码及思路：
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
28
29
30
31
32
33
| #include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110, M = 1010, mod = 1e9 + 7;
int vals[N];
LL f[M];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> vals[i];
sort(vals + 1, vals + n + 1);
f[0] = 1;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(i >= vals[j])
f[i] = (f[i] + f[i - vals[j]]) % mod;
cout << f[m] << endl;
return 0;
}
|
稍微解释一下为什么要把背包体积放第一维，物品编号放第二维就可以算出考虑顺序的方案数。
原始状态表示为f[j][i]，即当BOSS的血量为 i 时，小明的最后一次攻击能恰好击杀时使用的是第 j 张牌的总方案数。此时在BOSS血量为某一确定值的前提下，需要循环遍历所有牌并判断其是否能作为此时的最后一击，这里其实就暗含了一个出牌的顺序。
优化成一维也很显然，即满足公式f[i] += f[i - vals[j]]，含义为血量为 i 时考虑顺序差异的方案总数。