Card Game (打表, 递推)
题意
给出 $n$ 个堆，第一个堆上放了 $k$ 张值分别为 $1,2,3...k$ 的卡牌，在这 $n$ 个堆上跑加强的汉诺塔问题。要求如果一个值为 $x$ 的卡牌上有其他牌，那么他一定得是 $x-1$。问 $k$ 的最大值可以是多少。
思路
不是很严谨的证明。因为每一张值为 $x$ 的卡牌都严格要求自己的上面必须是 $x-1$，所以我们尽可能少地占用堆显然是更优的。
首先假设已知 $m$ 个堆时最多在第一个堆可以放 $f_m$ 张牌，那么在 $m+1$ 个堆的情况下，显然我们可以通过先把最顶上的 $1$ 放到新加进来的堆上，然后将其他 $f_m$ 张牌移到另一个堆 $H_1$ 上，然后再把值为 $1$ 的牌移回 $H_1$。
也就是说我们可以先移 $f_m+1$ 张牌到另外一个堆 $H_1$ 上。那么此时我们还剩下 $m$ 个堆可用，所以我们可以再移 $f_m$ 张牌到另一个堆 $H_2$ 上。接下来，我们要把 $H_1$ 的牌移到 $H_2$ 上。
理论上，$m$ 个堆是不够我们移动 $f_m+1$ 张牌的。但是，实际上，当我们先将 $H_1$ 上的 $f_m$ 张牌移出去后，$H_1$ 最底下一张牌实际上可以直接放到 $H_2$ 顶上。所以这样我们就将 $H_1$ 上的 $f_m+1$ 张牌移到了 $H_2$ 顶部。
故结论是 $f_n=f_{n-1}*2+1$。然后因为 $f_2 = 1$，有 $f_n=2^{n-1}+1$。
Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define orep(i, l, r) for(auto i = (l); i < (r); ++i)
#define NL std::cout << '\n'
using lnt = long long;
const int mo = 998244353;
lnt ksm(lnt x, lnt e) {
lnt ret = 1;
while (e) {
if (e & 1) { (ret *= x) %= mo; }
(x *= x) %= mo; e >>= 1;
}
return ret;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) {
lnt x; std::cin >> x;
std::cout << ksm(2, x-1)-1; NL;
}
return 0;
}Klee likes making friends (dp, 模m滚动)
题意
给出有 $n$ 个点的序列 $A$，第 $i$ 个点的权重为 $A_i$，现要求从这 $n$ 个点里选一个子序列，满足原序列中每连续 $m$ 个点中至少有 $2$ 个点被选中，同时最小化被选出的序列的权重和。
$2 \le n \le 20000$, $2 \le m \le 2000$, $m \le n$
思路
如果我们一开始设 $dp[i]$ 的值为前 $i$ 个满足每 $m$ 个点至少有两个点被选中的要求且第 $i$ 个被选上的最小权重和，会发现在转移的时候缺少了信息。比如如果写出 $dp[i] = dp[i-m]+A[i]$，这时是不能确定 $[i-m-1, i-1]$ 这个区间上被选中的点数是否大于等于二的。所以需要再加上一个信息，即设 $dp[i][k]$ 表明前 $i$ 个满足条件、同时在 $[i-k, i]$ 这个区间内至少有两个点被选中的最小权重和。这样只需贪心地保证 $[i-m-1, i-1]$ 满足条件即可。因为在$[i-m-1, i-1]$满足条件的情况下，对于任意的$x>1$，$[i-m-x, i-x]$都满足条件。
此时就可以确定 $dp[i][k] = min(dp[i][k-1], dp[i-k][m-k])$ 了。
这里需要注意下在整个序列的前 $m$ 个的 $dp[i][0]$ 不需要初始化为 $+\infty$，因为在处理前 $m$ 个数的时候还没有形成一个长为 $m$ 个连续段。实际上只需要默认 $[0, n-1]$ 以外的数都被选了就行。
然后模 $m$ 滚动优化一下空间。
Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define NL std::cout << '\n'
using lnt = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
const int inf = 0x3f3f3f3f;
while (t--) {
int n, m; std::cin >> n >> m;
std::vector<int> v(n);
for (auto &x : v) { std::cin >> x; }
std::vector dp(m, std::vector<int>(m));
for (int i = 0, id = i%m; i < n; ++i, ++id == m ? id = 0 : 0) {
dp[id][0] = inf;
for (int j = 1; j < m; ++j) {
dp[id][j] = std::min({dp[id][j-1], dp[(id-j) < 0 ? id-j+m : id-j][m-j]+v[i]});
}
}
int ret = inf;
for (int i = n-m+1, id = i%m; i < n; ++i, ++id == m ? id = 0 : 0) {
ret = std::min(ret, dp[id][i-(n-m)]);
}
std::cout << ret; NL;
}
return 0;;
}