题解：T496174 「金坷垃杯 R1」十三太保

· · 题解

出题人官方题解~

其实这种计数问题无非就 3 种方法：

  1. 爆搜，dfs 枚举所有情况
  2. 数学方法，计算
  3. dp

显然这题不让你搜，数学方法又没有，那就只能 dp 了。

然后来看题。数列中每个数字只能选择一次，因此抽象过来就是这样的：

01 背包问题，求正好能选数选成 k 的方案数。

这不就是板题了吗……

按照“题目问什么，状态设什么”的状态定义原则，定义 dp_{i, j} = 前 i 个数中选数使和正好为 j 的方法数。转移也很显然，是 dp_{i, j} = dp_{i - 1, j - a_i} + dp_{i,j - 1}。

注意要用滚动数组优化，不然就是 MLE。

std:

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e7 + 10;
int k, n, a[N], dp[N];

template <typename T>

inline T read() {
    T sum = 0, fl = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}

template <typename T>

inline void write(T x) {
    if (x < 0) {
        putchar('-'), write<T>(-x);
        return;
    }
    static T sta[35];
    int top = 0;
    do { sta[top++] = x % 10, x /= 10; } while (x);
    while (top) putchar(sta[--top] + 48);
}

int main() {
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = k; j >= a[i];j--) dp[j] += dp[j - a[i]];
    cout << dp[k] << endl;
    return 0;
}