2022——蓝桥杯十三届2022国赛大学B组真题

问题分析

看到这个问题的同学很容易想到用十层循环暴力计算，反正是道填空题，一直算总能算得出来的，还有些同学可能觉得十层循环太恐怖了，写成回溯更简洁一点。像下面这样

#include <bits/stdc++.h>
using namespace std;
int cnt=0;
vector<bool> used(2023,false);
void dfs(int now,int len,int start) {
	if(len==10){
		if(now==2022){
			cnt++;
		}
		return;
	}
	for(int i=start;i<=2022-now;i++){
		if(!used[i]){
			used[i]=true;
			dfs(now+i,len+1,i+1);
			used[i]=false;
		}
	}
}
int main() {
	dfs(0,0,1);
	cout<<cnt<<endl;
	return 0;
}

但是我们分析一下，这个时间复杂度大概是$O(C_{2022}^{10})$级别的，这个数字太恐怖了，要高于$10^{30}$的数量级，而c++代码在平台上运行的速度大概是$10^9$次每秒。所以，根本不可能暴力求出答案。而回溯不可以，我们可以动态规划嘛。这实际上就是典型的限量背包问题（如果不知道什么是限量背包问题，可以看我的这篇博客）。从物品（1~2022）中挑选10个物品，要求每种物品只能选一次，然后装满该背包（容量2022）有多少种组合？将该问题转化为背包问题就很容易解决了。（不过要记得用long long，这个数字很大）

具体代码如下

#include<iostream>
using namespace std;
long long int f[11][2023]= {0}; //f[j][k]:选择了j个物品满载容积k的背包的组合数 
int i, j, k;
int main() {
	f[0][0]=1;
	for(i=1; i<=2022; i++) {//遍历每个物品 
		for(k=2022; k>=i; k--) {//遍历背包容量，从后往前遍历 
			for(j=1; j<=10; j++) {//遍历每个选择数量 
				f[j][k]+=f[j-1][k-i];
			}
		}
	}
	cout << f[10][2022];
	return 0;
}

结果