买蛋糕
非常标准的普及组题目。
有一个结论：假设选择的元素为 \(A_1\sim A_k\)，且满足 \(A_i < A_{i + 1}(1 \le i <n)\)，那么当 \(a_1 = 1\) 且 \(\forall 2\le i \le n, A_i \le 1+\sum_{j = 1}^{i - 1}A_j\) 时，\(1\sim \sum A_i\) 内的元素全部都可以被表示。证明可以考虑手动做一个背包可达性，应该是很显然的。
因为要保证每个数最多只被用一次，所以我们考虑外层枚举每一个数，然后内层枚举背包的体积，判断一下转移是否合法即可。时间复杂度 \(O(n^2)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
using pl = pair<int, ll>;
const int N = 1005;
const int inf = 0x3f3f3f3f;
int n;
pl dp[2 * N];
void upd(pl &x, pl y)
{if(y.fi < x.fi) x = y;else if(x.fi == y.fi) x.se += y.se;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;fill(dp, dp + 2 * n + 1, make_pair(inf, 0ll));dp[1] = {1, 1};for(int i = 2; i <= n; i++){for(int j = 2 * n; j >= i; j--){if(i <= min(n, j - i + 1))upd(dp[j], {dp[j - i].fi + 1, dp[j - i].se});}}pl ans = {inf, 0};for(int i = n; i <= 2 * n; i++)upd(ans, dp[i]);cout << ans.fi << " " << ans.se;return 0;
}