T1：四次方的和
给出 \(n\) 个正整数 \(a_1,~a_2,~\cdots,~a_n\)。选择其中总和不超过 \(m\) 的若干数，每个数只能选 \(1\) 次，选出的数的 \(4\) 次方之和最大是多少？
限制：
- \(1 \leqslant n \leqslant 4000\)
- \(1 \leqslant m \leqslant 10^4\)
- \(1 \leqslant a_i \leqslant 10^4\)
算法分析
本题难度简单，01背包模板题。直接使用二维数组会爆内存，需要空间优化
\(a_i\)：物品体积
\(a_i^4\)：物品价值
记 dp[i][j] 表示从 \(a_1 \sim a_i\) 中选和不超过 \(j\) 的数可得到的最大 \(4\) 次方之和
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(ll& x, ll y) { if (x < y) x = y; }
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> dp(m+1);
rep(i, n) {
for (int j = m; j >= a[i]; --j) {
ll x = (ll)a[i]*a[i]*a[i]*a[i];
chmax(dp[j], dp[j-a[i]]+x);
}
}
cout << dp[m] << '\n';
return 0;
}
T2：能量珠
小猴乘坐火箭到了 Mars 星球上，Mars 星上有很多能量珠。
小猴找到了 \(n\) 个能量珠，第 \(i\) 个能量珠的大小为 \(a_i\)。两个能量珠通过连接，可以释放出能量，一个大小为 \(x\) 和一个大小为 \(y\) 的能量珠连接，可以释放出的能量为 \(x \times y\)。
小猴打算选取总大小不超过 \(m\) 的能量珠，把它们按照序号从小到大的顺序，依次连接在一起，求他能得到的最大能量。
例如，小猴选取大小为 \(1,2,5,10\) 的能量珠，他可以获得的能量为 \(1 \times 2 + 2\times 5 + 5\times 10 = 62\)。
限制：
- \(1 \leqslant n \leqslant 100\)
- \(1 \leqslant m \leqslant 5000\)
- \(1 \leqslant a_i \leqslant 1000\)
算法分析
本题难度中等，类似最长上升子序列，区别是增加了一个总大小的限制。用两个维度分别记录最后拿出的珠子和珠子的总大小。状态转移时，枚举上一个珠子是什么。
记 dp[i][j] 表示从前 \(i\) 个珠子中选取总大小不超过 \(j\) 的珠子能得到的最大能量
转移：
取 \(a_i\)
dp[i][j] = dp[i-1][j-ai] + ai*ai上一个珠子的大小
但这里不知道 \(a_i\) 上一个珠子是什么，可以将这个信息加到 \(dp\) 定义中
想法：
dp[i][j]：以 \(a_i\) 结尾且总大小 \(\leqslant j\) 时能得到的最大能量
转移：
dp[i][j]：枚举 \(a_i\) 上一个珠子是什么
\( dp[i][j] = \max(dp[i][j], dp[k][j-a_i] + a_k \times a_i) \)
细节：
- 当 \(a_i\) 没有上一个时，只有 \(1\) 个珠子，无法有能量，\(dp[i][j]\) 保留初值 \(0\)，所以不用做多余操作
- 上一个珠子能不能是 \(a_k\) ？以 \(a_k\) 结尾的珠子总大小是 \(j-a_i\)，这要求 \(j-a_i\) 中至少有 \(a_k\) 的大小
答案：\(dp[1\sim n][m]\) 中的最大值
时间复杂度：\(O(n^2m)\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int dp[105][5005];
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n)rep(j, m+1) {
int now = 0;
rep(k, i) if (j-a[i] >= a[k]) {
chmax(now, dp[k][j-a[i]] + a[k]*a[i]);
}
dp[i][j] = now;
}
int ans = 0;
rep(i, n) chmax(ans, dp[i][m]);
cout << ans << '\n';
return 0;
}