2022蓝桥杯国赛

题目描述：

思路：

题主用了两个方法，一个是三维数组，1到2022个数可以当成编号，f[i][j][k]表示前i个数选了j个数总和为k，存在是否选择第i个数的问题，选择第i个数为f[i-1][j-1][k-i];没有选择第i个数则为f[i-1][j][k];

另一个方法为二维数组；

AC代码：

二维数组：

#include <iostream>
using namespace std;
long long dp[11][2023];
//dp[j][k]表示前j个数的总和为k;
int main()
{
    dp[0][0] = 1;//
    for (int i = 1; i <= 2022; i++) {   //物品的编号循环
        for (int j = 10; j >= 1; j--) {   //选择的数量循环
            for (int k = i; k <= 2022; k++) {  //从i开始是因为后续的k-i可能会数组越界
                dp[j][k] += dp[j - 1][k - i];//即未选择i时已经选择了j件物品总和为k，和选择了第i件物品后j件物品总和为k
            }
        }
    }
    cout << dp[10][2022];
}

 三维数组：

#include <iostream>
using namespace std;
long long f[2023][11][2023];  //f[i][j][k]表示前i个数选择j个后总和为K;
int main()
{
    for (int i = 0; i <= 2022; i++) {
        f[i][0][0] = 1;
    }
    for (int i = 1; i <= 2022; i++) {       //数的编号
        for (int j = 1; j <= 10; j++) {     //已选择的个数
            for (int k = 1; k <= 2022; k++) {    
                f[i][j][k] = f[i - 1][j][k];  //未选择第i个数就已经总和为k的情况
                if (k >= i) {    //数组存在k-i的情况可能会越界，因此此处需要判断
                    f[i][j][k] += f[i - 1][j - 1][k - i];  //选择第i个数后总和为K;
                }
            }
        }
    }
    cout << f[2022][10][2022];
    return 0;
}