当前位置：首页 > article >正文

【备战蓝桥杯国赛-国赛真题】2022

article 2024/11/17 23:59:30

在这里插入图片描述

思路

题目的一是就是从1~2022这2022个数中挑选十个数，使其的总和为2022，如果做过背包问题，那么思路就很好出来了，每个数无非就是选与不选，每个数有他们的权值，权值就等于它们本身的值，抽象成背包问题就是，每个物品只能选一次，且只能选十个，不能少也不能多，最终这十个数的综合为2022。我们可以定义状态数组： $f [2022] [10] [2022]$ ， $f [i] [j] [k]$ 表示前i个物品中选了j件物品，其中总和为k的方案数，状态转移为：

在这里插入图片描述

代码（C++）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL; 

const int N = 2050;

int n;
LL f[N][15][N]; // f[i][j][k] : 前i个物品中选了j件物品，其中总和为k的方案数 

int main() {
	n = 2022;
	for(int i = 0; i <= n; i ++) f[i][0][0] = 1;
	
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= 10; j ++)
			for(int k = 1; k <= n; k ++) {
				f[i][j][k] = f[i - 1][j][k]; // 不选第i个数 
				if(k - i >= 0) {
					f[i][j][k] += f[i - 1][j - 1][k - i]; // 选第i个数 
				}
			}
	
	cout << f[n][10][n] << "\n";
	return 0;
}