试题A
该题是一道背包dp题，我的思路是定义三维dp，第一维表示第i个数，第二维表示前i个数的总和为j，第三维表示前i个数，总和为j,第i个数为z的方案数。
首先观察这个题的性质，要求互不相同，首先我们需要找一个严格递增的序列，并且序列的总和为2022
刚开始我也是想到的一个O(n3)的dp 状态转移，但是我们发现其中一维可以通过优化去掉变成O(n2)dp，然后成功算出答案。
需要注意的是需要开 l o n g l o n g long long longlong因为答案太大爆int
然后推出方程式：
i f ( k > z ) c o n t i n u e ; / / 表 明 当 前 总 和 装 不 下 当 前 项 if(k > z) continue ; //表明当前总和装不下当前项 if(k>z)continue;//表明当前总和装不下当前项
i f ( k a n d z > = k ) / / 我 们 可 以 给 当 前 枚 举 项 加 一 构 造 新 的 方 案 if(k and z >= k) //我们可以给当前枚举项加一构造新的方案 if(kandz>=k)//我们可以给当前枚举项加一构造新的方案
f [ i ] [ z ] [ k ] + = f [ i − 1 ] [ z − k ] [ k − 1 ] ; f[z][k] += f[i - 1][z - k][k - 1] ; f[z][k]+=f[i−1][z−k][k−1];
i f ( z a n d k ) / / 表 明 我 们 选 的 当 前 项 必 须 比 上 一 项 严 格 大 if(z and k)//表明我们选的当前项必须比上一项严格大 if(zandk)//表明我们选的当前项必须比上一项严格大
f [ i ] [ z ] [ k ] + = f [ i ] [ z − 1 ] [ k − 1 ] ; f[z][k] += f[z - 1][k - 1] ; f[z][k]+=f[z−1][k−1];
代码如下
[code]#include #include #include using namespace std ;long long ans ;long long f[20][3000][3000] ; // 个数 总和 上一项int main(void){ f[0][0][0] = 1 ; for(int i = 1 ; i
